写点什么

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

  • 2022-11-05
    北京
  • 本文字数:1540 字

    阅读完需:约 5 分钟

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代码

发布于: 刚刚阅读数: 3
用户头像

还未添加个人签名 2021-02-15 加入

还未添加个人简介

评论

发布
暂无评论
2022-11-05:给定一个逆波兰式,转化成正确的中序表达式。要求只有必要加括号的地方才加括号。_算法_福大大架构师每日一题_InfoQ写作社区