中缀
人类正常使用的计算表达式即为中缀表达式比如:( 1 + 2 ) * 3 - 4
前缀
前缀表达式的计算逻辑为从右至左扫描,遇到数字入栈,遇到操作符,弹出两个数字运算然后将结果入栈,重复以上过程直到表达式最左端,最后运算得出的值即为表达式的结果
( 1 + 2 ) * 3 - 4
的前缀表达式为 - * + 1 2 3 4
后缀
( 1 + 2 ) * 3 - 4
的后缀1 2 + 3 * 4 -
后缀表达式的计算逻辑为从左至右扫描,遇到数字入栈,遇到操作符,弹出两个数字运算然后将结果入栈,重复以上过程直到表达式最右端,最后运算得出的值即为表达式的结果
中缀表达式转后缀表达式算法
- 初始化两个栈:运算符栈
s1
和操作数栈s2
- 从左至右扫描中缀表达式
- 遇到操作数时,将其压
s2
- 遇到运算符时,比较其与
s1
栈顶运算符的优先级:
4.1 如果s1
为空,或栈顶运算符为左括号(
,则直接将此运算符入栈
4.2 否则,若优先级比栈顶运算符的高,也将运算符压入s1
4.3 否则,将s1
栈顶的运算符弹出并压入到s2
中,再次转到4.1与s1
中新的栈顶运算符相比较 - 遇到括号时:
5.1 如果是左括号(
,则直接压入s1
5.2 如果是右括号)
,则依次弹出s1
栈顶的运算符,并压入s2
,直到遇到左括号为止,此时将这一对括号丢弃 - 重复步骤2至5,直到表达式的最右边
- 将
s1
中剩余的运算符依次弹出并压入s2
- 依次弹出
s2
中的元素并输出,结果的逆序即为中缀表达式对应的后缀表达式
简单的来说就是:
- 碰到操作数直接入
s2
- 碰到操作符的优先级比栈顶元素高的话就需要入栈,否则就从
s1
中弹出操作符,压入s2
,并继续上述过程,最后该操作符肯定是要入栈的
网友评论