Skip to content

Latest commit

 

History

History
105 lines (94 loc) · 6.65 KB

前中后缀表达式.md

File metadata and controls

105 lines (94 loc) · 6.65 KB

算数表达式在编程中分为: 前缀表达式, 中缀表达式以及 后缀表达式. 他们之间的区别在于运算符相对于操作数的位置不同: 前缀表达式的运算符位于与其相关的操作数之前; 中缀和后缀同理.

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

中缀表达式

是一种通用的算数或逻辑公式表示方法, 操作符以中缀形式处于操作数的中间. 中缀表达式是人们常用的算数表示方法. 虽然人的大脑很容易理解与分析中缀表达式, 但对于计算机来说中缀表达式却是很复杂的, 因此计算表达式的值时, 通常需要先将中缀表达式转化为前缀或后缀表达式, 然后进行求值. 对计算机来说, 计算前缀或后缀表达式的值非常简单.

前缀表达式

前缀表达式的运算符位于操作数之前.

前缀表达式的求值

从右至左扫描表达式, 遇到数字时, 将数字入栈, 遇到运算符时, 弹出栈顶的两个数, 用运算符与他们做相应的计算 (栈顶元素 op 次顶元素), 并将结果入栈; 重复上述过程直到表达式最左端, 最后运算得出的值即为表达式的结果. 计算 栗子 中的前缀表达式:

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

中缀表达式转化前缀表达式:

遵循以下步骤:

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

eg: 将中缀表达式1+((2+3)×4)-5转换为前缀表达式的过程如下:

扫描到的元素 S2(栈底 -> 栈顶) S1(栈底 -> 栈顶) 说明
5 5 空 数字, 直接入栈S2
- 5 - S1为空, 运算符直接入栈S1
) 5 - ) 右括号直接入栈S1
4 5 4 - ) 数字直接入栈S2
* 5 4 - ) * S1栈顶是右括号, 直接入栈S1
) 5 4 - ) * ) 右括号直接入栈S1
3 5 4 3 - ) * ) 数字直接入栈S2
+ 5 4 3 - ) * ) + S1栈顶为右括号直接入栈S1
2 5 4 3 2 - ) * ) + 数字直接入栈S2
( 5 4 3 2 + - ) * 左括号, 弹出S1运算符直至遇到右括号
( 5 4 3 2 + * - 同上
+ 5 4 3 2 + * - + 优先级与-相同, 入栈S1
1 5 4 3 2 + * 1 - + 数字直接入栈S2
到达最左端 5 4 3 2 + * 1 + - 空 S1依次出栈 入栈S2
得到结果- + 1 * + 2 3 4 5.

后缀表达式

后缀表达式与前缀表达式类似, 只是运算符位于操作数之后.

后缀表达式的求值

与前缀表达式类似, 只是顺序从左至右: 从左至右扫描表达式, 遇到数字时, 将数字入栈. 遇到运算符时, 弹出栈顶的两个数, 用运算符对它们做相应的计算 (次顶元素 op 栈顶元素), 并将结果入栈; 重复上述过程直到表达式最右端, 最后运算得出的值即为表达式的结果.

eg: 后缀表达式3 4 + 5 * 6 -

  1. 从左至右扫描, 将3和4入栈;
  2. 遇到+运算符, 弹出4和3(4为栈顶元素, 3为次顶元素, 注意与前缀表达式作比较), 计算3 + 4将结果7入栈;
  3. 将5入栈;
  4. 接下来是*运算符, 因此弹出5和7, 计算7 * 5将结果35入栈;
  5. 将6入栈;
  6. 最后是-运算符, 计算35 - 6得出最终结果29;

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

与转换前缀表达式相似, 遵循以下步骤:

  1. 初始化两个栈: 运算符栈S1和存储中介结果的栈S2;
  2. 从左至右扫描中缀表达式;
  3. 遇到操作数, 压入S2;
  4. 遇到运算符, 比较其与S1栈顶运算符的优先级:
    1. 如果S1为空或栈顶运算符为左括号(, 则直接将此运算符入栈S1;
    2. 否则, 若优先级比栈顶运算符的高, 也将运算符压入S1 (注意转换为前端表达式时是优先级较高或相同, 而这里则是不包括相同的情况);
    3. 否则, 将S1栈顶的运算符弹出并压入S2中, 再次转到 4.1 与S1中新的栈顶运算符相比较;
  5. 遇到括号时:
    1. 如果是左括号(, 则直接压入S1;
    2. 如果是右括号), 则依次弹出S1栈顶的运算符, 并压入S2, 直至遇到左括号, 此时将这一对括号丢弃;
  6. 重复步骤 2 至 5 , 知道表达式的最右边;
  7. 将S1中剩余的运算符依次弹出并压入S2;
  8. 依次弹出S2中的元素并输出, 结果是逆序即为中缀表达式对应的后缀表达式 (注意: 转换前缀表达式时不用逆序);

eg: 将中缀表达式1+((2+3)×4)-5转换为后缀表达式的过程如下

扫描到的元素 S2(栈底 -> 栈顶) S1(栈底 -> 栈顶) 说明
1 1 空 数字直接入S2
+ 1 + S1为空直接入栈
( 1 + ( 左括号直接入S1
( 1 + ( ( 同上
2 1 2 + ( ( 数字直接入栈S2
+ 1 2 + ( ( + 栈顶为左括号 直接入栈S1
3 1 2 3 + ( ( + 数字 直接入栈S2
) 1 2 3 + + ( 右括号, 弹出运算符直至遇到左括号
* 1 2 3 + + ( * 栈顶为左括号 直接入栈S1
4 1 2 3 + 4 + ( * 数字 直接入栈S2
) 1 2 3 + 4 * + 右括号, 弹出运算符直至遇到左括号
- 1 2 3 + 4 * + - -与+优先级相同, S1弹出+, 再压入-
5 1 2 3 + 4 * + 5 - 数字 直接入栈S2
到达最右端 1 2 3 + 4 * + 5 - 空 弹出剩余S1中运算符 压入S2
得到结果1 2 3 + 4 * + 5 -. (注意: 需要逆序输出).