1
2022-11-05:给定一个逆波兰式,转化成正确的中序表达式。要求只有必要加括号的地方才加括号。
作者:福大大架构师每日一题
- 2022-11-05 北京
本文字数:1540 字
阅读完需:约 5 分钟
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());
}
复制代码
执行结果如下:
划线
评论
复制
发布于: 刚刚阅读数: 3
版权声明: 本文为 InfoQ 作者【福大大架构师每日一题】的原创文章。
原文链接:【http://xie.infoq.cn/article/465e8fdd44e93565a3468145e】。
本文遵守【CC-BY 4.0】协议,转载请保留原文出处及本版权声明。
福大大架构师每日一题
关注
还未添加个人签名 2021-02-15 加入
还未添加个人简介
评论