前置知识点
数学表达式的三种形式:前缀表达式,中缀表达式,后缀表达式。
中缀表达式(Infix Expression)
<font color="#ff0000">就是我们平时常用的书写方式,带有括号</font>
前缀表达式(Prefix Expression)
要求运算符出现在运算数字的前面
后缀表达式(Postfix Expression)
要求运算符出现在运算数字的后面
思路
步骤一: 中缀表达式转化为后缀表达式
遍历中缀表达式
遇到左括号( -> 压入栈中
遇到数字 -> 追加到后缀表达式
遇到运算符<br>
栈中无运算符 -> 压入栈中
栈中有运算符 -> 比较栈顶运算符
栈顶运算符 >= 当前运算符
当前运算符压入栈中
栈顶运算符 < 当前运算符
栈顶运算符弹出,追加到后缀表达式<br>当前运算符压入栈中<br>
遇到右扩符) -> 栈顶运算符弹出,追加到后缀表达式<br> 删除栈中左扩符
步骤二: 后缀表达式求值
遍历表达式
遇到数字 -> 压进栈中
遇到运算符 -> 弹出2个数字,进行运算 -> 结果压进栈中
遍历结束 -> 返回栈顶元素