2022-11-05:给定一个逆波兰式,转化成正确的中序表达式。要求只有必要加括号的地方才加括号。

2022-11-05:给定一个逆波兰式,转化成正确的中序表达式。要求只有必要加括号的地方才加括号。

答案2022-11-05:

代码用rust编写。代码如下:

计算结果。用栈。遇到数字,入栈;遇到运算符,出栈。
给出表达式,难点在于去掉没必要的小括号。准备两个栈,一个栈存数字,另一个栈存类型,类型有数字类型,加减类型,乘除类型。最有可能加括号的一定是后来的乘除类型遇到先来的加减类型。

执行结果如下:

fn main() {
    let rpn = "3 -5 13 + * 6 2 3 - 2 + / + 4 5 3 * * -";
    println!("{}", get_ans(rpn));
    println!("{}", convert(rpn));
}

// 请保证给定的逆波兰式是正确的!
fn get_ans(rpn: &str) -> i32 {
    if rpn == "" {
        return 0;
    }
    let parts: Vec<&str> = rpn.split(" ").collect();
    let mut stack: Vec<i32> = vec![];
    for part in parts.iter() {
        if *part == "+" || *part == "-" || *part == "*" || *part == "/" {
            let right = stack.pop().unwrap();
            let left = stack.pop().unwrap();
            let mut ans: i32 = 0;
            if *part == "+" {
                ans = left + right;
            } else if *part == "-" {
                ans = left - right;
            } else if *part == "*" {
                ans = left * right;
            } else {
                ans = left / right;
            }
            stack.push(ans);
        } else {
            let a: i32 = part.parse().unwrap();
            stack.push(a);
        }
    }
    // stack 只有一个数,最终的结果
    return stack.pop().unwrap();
}

#[derive(PartialEq)]
enum Operation {
    SingleNumber,
    AddOrMinus,
    MultiplyOrDivide,
}

// 请保证输入的逆波兰式是正确的
// 否则该函数不保证正确性
// 逆波兰式仅支持+、-、*、/
// 想支持更多算术运算符自己改
fn convert(rpn: &str) -> String {
    if rpn == "" {
        return String::from("");
    }
    let parts: Vec<&str> = rpn.split(" ").collect();
    let mut stack1: Vec<String> = vec![];
    let mut stack2: Vec<Operation> = vec![];
    for cur in parts.iter() {
        // cur 当前遇到的字符串
        // +- */ 单数
        if *cur == "+" || *cur == "-" {
            let b = stack1.pop().unwrap();
            let a = stack1.pop().unwrap();
            stack2.pop();
            stack2.pop();
            stack1.push(format!("{}{}{}", a, cur, b));
            stack2.push(Operation::AddOrMinus);
        } else if *cur == "*" || *cur == "/" {
            let b = stack1.pop().unwrap();
            let a = stack1.pop().unwrap();
            let b_op = stack2.pop().unwrap();
            let a_op = stack2.pop().unwrap();
            let left = if a_op == Operation::AddOrMinus {
                format!("({})", a)
            } else {
                a
            };
            let right = if b_op == Operation::AddOrMinus {
                format!("({})", b)
            } else {
                b
            };
            stack1.push(format!("{}{}{}", left, cur, right));
            stack2.push(Operation::MultiplyOrDivide);
        } else {
            stack1.push(String::from(*cur));
            stack2.push(Operation::SingleNumber);
        }
    }
    return String::from(stack1.pop().unwrap());
}

执行结果如下:

在这里插入图片描述


左神java代码

本作品采用《CC 协议》,转载必须注明作者和本文链接
微信公众号:福大大架构师每日一题。最新面试题,涉及golang,rust,mysql,redis,云原生,算法,分布式,网络,操作系统。
讨论数量: 0
(= ̄ω ̄=)··· 暂无内容!

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容,与人为善,比聪明更重要!