前缀、中缀、后缀表达式


概念

(3 + 4) × 5 - 6  > 中缀表达式
- × + 3 4 5 6    > 前缀表达式
3 4 + 5 × 6 -    > 后缀表达式

1. 前缀表达式(前缀记法、波兰式)

计算机求值

例如前缀表达式“- × + 3 4 5 6”
  1. 从右至左扫描,将 6、5、4、3 压入堆栈;
  2. 遇到+运算符,因此弹出 3 和 4( 3 为栈顶元素,4 为次顶元素,注意与后缀表达式做比较),计算出 3 + 4 的值,得 7 ,再将 7 入栈;
  3. 接下来是 × 运算符,因此弹出7和5,计算出 7 × 5 = 35,将 35 入栈;
  4. 最后是-运算符,计算出 35 - 6 的值,即 29,由此得出最终结果

将中缀表达式转换为前缀表达式

  1. 初始化两个栈:运算符栈S1和储存中间结果的栈S2;
  2. 从右至左扫描中缀表达式;
  3. 遇到操作数时,将其压入S2;
  4. 遇到运算符时,比较其与S1栈顶运算符的优先级:
    (4-1) 如果 S1 为空,或栈顶运算符为右括号“)”,则直接将此运算符入栈;
    (4-2) 否则,若优先级比栈顶运算符的较高或相等,也将运算符压入 S1;
    (4-3) 否则,将 S1 栈顶的运算符弹出并压入到 S2 中,再次转到(4-1)与 S1 中新的栈顶运算符相比较;
  5. 遇到括号时:
    (5-1) 如果是右括号“)”,则直接压入 S1;
    (5-2) 如果是左括号“(”,则依次弹出 S1 栈顶的运算符,并压入 S2,直到遇到右括号为止,此时将这一对括号丢弃;
  6. 重复步骤(2)至(5),直到表达式的最左边;
  7. 将 S1 中剩余的运算符依次弹出并压入 S2;
  8. 依次弹出 S2 中的元素并输出,结果即为中缀表达式对应的前缀表达式。
eg. 1+((2+3)×4)-5
ElementS1S2
55Null
-5-
)5- )
454- )
*54- ) *
)54- ) * )
3543- ) * )
+543- ) * ) +
25432- ) * ) +
(5432+- ) *
(5432+*-
+5432+*- +
15432+*1- +
End5432+*1+-Pull

2. 后缀表达式(后缀记法、逆波兰式)

计算机求值

例如后缀表达式“3 4 + 5 × 6 -”
  1. 从左至右扫描,将 3 和 4 压入堆栈;
  2. 遇到+运算符,因此弹出 4 和 3( 4 为栈顶元素,3 为次顶元素,注意与前缀表达式做比较),计算出 3 + 4 的值,得 7,再将 7 入栈;
  3. 将5入栈;
  4. 接下来是×运算符,因此弹出 5 和 7,计算出 7 × 5 = 35,将 35 入栈;
  5. 将 6 入栈;
  6. 最后是-运算符,计算出 35 - 6 的值,即 29,由此得出最终结果。

将中缀表达式转换为后缀表达式

  1. 初始化两个栈:运算符栈S1和储存中间结果的栈S2;
  2. 从左至右扫描中缀表达式;
  3. 遇到操作数时,将其压入 S2;
  4. 遇到运算符时,比较其与 S1 栈顶运算符的优先级:
    (4-1) 如果 S1 为空,或栈顶运算符为左括号“(”,则直接将此运算符入栈;
    (4-2) 否则,若优先级比栈顶运算符的高,也将运算符压入 S1(注意转换为前缀表达式时是优先级较高或相同,而这里则不包括相同的情况);
    (4-3) 否则,将 S1 栈顶的运算符弹出并压入到 S2 中,再次转到(4-1)与 S1 中新的栈顶运算符相比较;
  5. 遇到括号时:
    (5-1) 如果是左括号“(”,则直接压入 S1;
    (5-2) 如果是右括号“)”,则依次弹出 S1 栈顶的运算符,并压入 S2,直到遇到左括号为止,此时将这一对括号丢弃;
  6. 重复步骤(2)至(5),直到表达式的最右边;
  7. 将S1中剩余的运算符依次弹出并压入 S2;
  8. 依次弹出 S2 中的元素并输出,结果的逆序即为中缀表达式对应的后缀表达式(转换为前缀表达式时不用逆序)。
eg. 1+((2+3)×4)-5
ElementS1S2
11Null
+1+
(1+ (
(1+ ( (
212+ ( (
+12+ ( ( +
3123+ ( ( +
)123++ (
*123++ ( *
4123+4+ ( *
)123+4*+
-123+4*+-
5123+4*+5-
End123+4*+5-Null
Last modification:September 3rd, 2020 at 12:33 am
小编很用心去写文章的,大家伙们给点支持呗。