上一个帖子
主要两个知识点
- 将中缀表达式转换成后缀表达式
- 计算后缀表达式的结果
中缀表达式转换后缀表达式规则
- 所有数字直接输出
- 运算符优先级高于栈内的要入栈(或空栈), 否则从栈中弹出所有优先级更高或一样的运算符(或直到括号), 再将当前的入栈
- 所有左括号入栈
若是右括号, 栈不断出栈, 直到碰到左括号
>如果遇到操作符, 则从栈中弹出元素直到 栈顶操作符比当前操作符 优先级更低, 或者栈为空, 或者遇到左括号为止>比如当前操作符是 '+', '-' 都要把栈内所有的运算符都弹出并输出, 因为栈顶不可能有比加减优先级更低的操作符>再比如当前操作符是 '*', '/' 要把栈内所有的运算符都弹出并输出, 直到栈顶的运算符是 '+' 或者 '-'>弹出完这些元素后, 才将遇到的操作符压入到栈中>有一点需要注意, 只有在遇到 ')' 的情况下我们才弹出 '(' , 其他情况我们都不会弹出'('
计算后缀表达式
- 从左向右扫描, 遇到数字压栈
- 遇到操作符, 弹出栈顶的两个元素进行计算, 先弹出的元素在右边, 后弹出来的在左边
- 进行计算后, 将结果压栈
- 再往后扫描, 直到扫描结束, 输出栈顶元素, 即为最终结果
