前缀中缀和后缀表达式
2019-10-20 本文已影响0人
spraysss
中缀
人类正常使用的计算表达式即为中缀表达式比如：( 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，并继续上述过程，最后该操作符肯定是要入栈的
