中缀表达式转后缀表达式的思路步骤分析
- 初始化一个栈和一个队列,运算符栈
S1
和存储中间结果的队列Q1
- 从左至右扫描中缀表达式
- 遇到操作数时放入队列
Q1
中 - 遇到运算符时仳较其与
S1
栈顶运算符的优先级- 如果
S1
为空,或栈顶运算符为左括号(
则直接将此运算符入栈 - 否则,若优先级比栈顶运算符的高也将运算符壓入
S1
- 否则,将
S1
栈顶的运算符弹出并添加到Q1
中再次转到(4.1)
与S1
中新的栈顶运算符相比较
- 如果
- 如果是左括号
(
,则直接压入S1
- 如果是右括号
)
则依次弹出S1
棧顶的运算符,并添加到Q1
直到遇到左括号为止,此时将这一对括号丢弃 - 重复步骤2至5直到表达式的最右边
- 将
S1
中剩余的运算符依次弹出并添加到Q1
- 依次取出
Q1
中的元素并输出,结果就是中缀表达式对应的后缀表达式
计算法方式很简单,创建一个栈S1
从左到右依次扫描表达式,遇到数值则放入栈中;遇到运算符则从栈S1
中弹出两个数值,并计算表达式的值然后重新入栈。
后缀表达式的计算比较简单这里就不實现代码了。有兴趣的同学可以自己实现以下