中缀表达式转换为后缀表达式
后缀表达式适合计算机进行运算,但是人却不太容易写出来,尤其是表达式很长的情况下,因此在开发中,我们需要将中缀表达式转成后缀表达式。
具体步骤如下:
1.初始化两个栈:运算符栈s1和储存中间结果的栈s2
2.从左至右扫描中缀表达式
3.遇到操作数时,将其压s2
4.遇到运算符时,比较其与s1栈顶运算符的优先级:
4.1 如果s1为空,或栈顶运算符为左括号"(",则直接将此运算符入栈
4.2 否则,若优先级比栈顶运算符高,也将运算符压入s1
4.3 否则,将s1栈顶的运算符弹出并压入到s2中,再次转到(4.1)与s1中新的栈顶运算符相比较
5.遇到括号时:
- 如果是左括号"(",则直接压入s1
- 如果是右括号")",则依次弹出s1栈顶的运算符,并压入s2,直到遇到左括号为止,此时将一对括号丢弃
6.重复步骤2至5,直到表达式的最右边
7.将s1中剩余的运算符依次弹出并压入s2
8.依次弹出s2中的元素并输出,结果的逆序即为中缀表达式对应的后缀表达式
中缀表达式1 + (( 2 + 3 ) x 4 ) - 5 ===>>后缀表达式
将s2出栈- 5 + x 4 + 3 2 1 ===>> 1 2 3 + 4 x + 5 -
扫描到的元素 | s2(栈底->栈顶) | s1(栈底->栈顶) | 说明 |
---|---|---|---|
1 | 1 | 空 | 数字,直接入栈 |
+ | 1 | + | s1为空,直接入栈 |
( | 1 | +( | 左括号,直接入栈 |
( | 1 | +(( | 左括号,直接入栈 |
2 | 12 | +(( | 数字,直接入栈 |
+ | 12 | +((+ | s1栈顶为左括号,运算符直接入栈 |
3 | 123 | +((+ | 数字,直接入栈 |
) | 123+ | +( | 右括号,弹出运算符直至遇到左括号 |
x | 123+ | +(x | s1栈顶为左括号,运算符直接入栈 |
4 | 123+4 | +(x | 数字,直接入栈 |
) | 123+4x | + | 右括号,弹出运算符直至遇到左括号 |
- | 123+4x+ | - | -与+优先级相同,因此弹出+,再压入- |
5 | 123+4x+5 | - | 数字,直接入栈 |
到达右端 | 123+4x+5- | 空 | s1中剩余的运算符 |