数据结构与算法(六)栈 ---前缀、中缀、后缀表达式(逆波兰表达式)

前言

前缀表达式、中缀表达式、后缀表达式都是四则运算的表达方式,用以四则运算表达式求值,即数学表达式的求值。

中缀表达式

简介

中缀表达式就是常见的运算表达式,如(3+4)×5-6

前缀表达式

简介

前缀表达式又称波兰式,前缀表达式的运算符位于操作数之前

比如:- × + 3 4 5 6

前缀表达式的计算机求值
  • 1)从右至左扫描表达式,
  • 2)遇到数字时,将数字压入堆栈,遇到运算符时,弹出栈顶的两个数,用运算符对它们做相应的计算(栈顶元素 op 次顶元素),并将结果入栈;
  • 3)重复上述过程直到表达式最左端,最后运算得出的值即为表达式的结果

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

转换步骤如下:
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中的元素并输出,结果即为中缀表达式对应的前缀表达式

后缀表达式

简介

后缀表达式又称逆波兰表达式,与前缀表达式相似,只是运算符位于操作数之后

比如:3 4 + 5 × 6 -

后缀表达式计算机求值

与前缀表达式类似,只是顺序是从左至右:

  • 1、从左至右扫描表达式
  • 2、遇到数字时,将数字压入堆栈,遇到运算符时,弹出栈顶的两个数,用运算符对它们做相应的计算(次顶元素op 栈顶元素 ),并将结果入栈
  • 3、重复上述过程直到表达式最右端,最后运算得出的值即为表达式的结果

例如后缀表达式“3 4 + 5 × 6 -”:

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

与转换为前缀表达式相似,步骤如下:

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中的元素并输出,结果的逆序即为中缀表达式对应的后缀表达式(转换为前缀表达式时不用逆序)

中缀表达式转化为前缀和后缀表达式

转化步骤:

  • 1、按照运算符的优先级对所有的运算单位加括号

  • 2、将运算符移动到对应括号的前面(前缀表达式)或后面(后缀表达式)

  • 3、去掉括号,得到前缀或后缀表达式

示例:
中缀表达式:1+(2+3)×4-5

1)加括号
式子变成 ((1+((2+3)×4))-5)

2)移动运算符

对于前缀表达式,变成了 -(+(1×(+(23)4))5)

对于后缀表达式:变成了((1((23)+4)×)+5)-

3)去掉括号
前缀表达式: - + 1 × + 2 3 4 5
后缀表达式:1 2 3 + 4 × + 5 -

参考:https://www.cnblogs.com/chensongxian/p/7059802.html
https://www.cnblogs.com/zzliu/p/10801113.html

# 数据结构   算法  

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×