前缀、中缀、后缀表达式
概念
(3 + 4) × 5 - 6 > 中缀表达式
- × + 3 4 5 6 > 前缀表达式
3 4 + 5 × 6 - > 后缀表达式
1. 前缀表达式(前缀记法、波兰式)
计算机求值
例如前缀表达式“- × + 3 4 5 6”
- 从右至左扫描,将 6、5、4、3 压入堆栈;
- 遇到+运算符,因此弹出 3 和 4( 3 为栈顶元素,4 为次顶元素,注意与后缀表达式做比较),计算出 3 + 4 的值,得 7 ,再将 7 入栈;
- 接下来是 × 运算符,因此弹出7和5,计算出 7 × 5 = 35,将 35 入栈;
- 最后是-运算符,计算出 35 - 6 的值,即 29,由此得出最终结果
将中缀表达式转换为前缀表达式
- 初始化两个栈:运算符栈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 中的元素并输出,结果即为中缀表达式对应的前缀表达式。
eg. 1+((2+3)×4)-5
Element | S1 | S2 |
---|---|---|
5 | 5 | Null |
- | 5 | - |
) | 5 | - ) |
4 | 54 | - ) |
* | 54 | - ) * |
) | 54 | - ) * ) |
3 | 543 | - ) * ) |
+ | 543 | - ) * ) + |
2 | 5432 | - ) * ) + |
( | 5432+ | - ) * |
( | 5432+* | - |
+ | 5432+* | - + |
1 | 5432+*1 | - + |
End | 5432+*1+- | Pull |
2. 后缀表达式(后缀记法、逆波兰式)
计算机求值
例如后缀表达式“3 4 + 5 × 6 -”
- 从左至右扫描,将 3 和 4 压入堆栈;
- 遇到+运算符,因此弹出 4 和 3( 4 为栈顶元素,3 为次顶元素,注意与前缀表达式做比较),计算出 3 + 4 的值,得 7,再将 7 入栈;
- 将5入栈;
- 接下来是×运算符,因此弹出 5 和 7,计算出 7 × 5 = 35,将 35 入栈;
- 将 6 入栈;
- 最后是-运算符,计算出 35 - 6 的值,即 29,由此得出最终结果。
将中缀表达式转换为后缀表达式
- 初始化两个栈:运算符栈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 中的元素并输出,结果的逆序即为中缀表达式对应的后缀表达式(转换为前缀表达式时不用逆序)。
eg. 1+((2+3)×4)-5
Element | S1 | S2 |
---|---|---|
1 | 1 | Null |
+ | 1 | + |
( | 1 | + ( |
( | 1 | + ( ( |
2 | 12 | + ( ( |
+ | 12 | + ( ( + |
3 | 123 | + ( ( + |
) | 123+ | + ( |
* | 123+ | + ( * |
4 | 123+4 | + ( * |
) | 123+4* | + |
- | 123+4*+ | - |
5 | 123+4*+5 | - |
End | 123+4*+5- | Null |