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


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

3.1 规则

  • 1、初始化栈和集合:运算符号栈s1和存储空间集合s2

  • 2、从左到右扫描中缀表达式

  • 3、遇到操作数时,将其加入s2

  • 4、遇到运算符时,比较其与s1栈顶运算符的优先级

    - 4.1、如果s1为空,或栈顶运算符为左括号‘(’,则直接将此运算符入栈
    - 4.2、否则,若优先级比栈顶运算符的高,也将运算符压入s1
    - 4.3、否则,将s1栈顶的运算符弹出并加入到s2中,再次转到 流程4
    
  • 5、遇到括号时:

    - 5.1、如果是左括号‘(’,则直接压入s1
    - 5.2、如果是右括号‘)’,则依次弹出s1栈顶的运算符,并且加入s2,直到遇到左括号为止,此时将这一对括号丢弃
    
  • 6、重复步骤 2-5,直到表达式的最右边

  • 7、将s1中剩余的运算符依次弹出并加入s2

  • 8、s2结果即为中缀表达式对应的后缀表达式

3.2 实例

以上面的转换为实例,比如输入 1 + ( ( 2 + 3 ) * 4 ) - 5,那么怎么转换成后缀表达式呢?

扫描到的元素 s2集合中元素 s1(栈底->栈顶) 说明
1 1 数字 直接加入到集合中
+ 1 + s1为空,直接入栈
( 1 +( 左括号 直接入栈
( 1 +( ( 同上
2 12 +( ( 数字
+ 12 +( (+ s1栈顶是左括号,运算符直接入栈
3 123 +( (+ 数字
) 123+ +( 右括号,弹出运算符直至遇到左括号
* 123+ +( * s1栈顶是左括号,运算符直接入栈
4 123+4 +( * 数字
) 123+4 * + 右括号,弹出运算符直至遇到左括号
- 123+4 *+ - -与+优先级相同,因此弹出+号,在压入-
5 123+4 *+ 5 - 数字
到达最右端 123+4 *+ 5 - s1中剩余的运算符

至此整个过程转换完毕

即中缀表达式1 + ( ( 2 + 3 ) 4 ) - 5 的后缀表达式为1 2 3 + 4 + 5 -

非原创原文链接:https://blog.csdn.net/qq_36144258/article/details/95075064


文章作者: 剑胆琴心
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 剑胆琴心 !
评论
 上一篇
python正则表达式 python正则表达式
常用正则表达式来对爬取的网页进行解析,但是正则表达式的构造稍微复杂一点,一般在结构化的网页中没必要用正则(易出错) # findall a = re.findall('jianeng',s ) ## 搜索字符串,以列表类型返回全部能匹配的
2020-02-17
下一篇 
ubuntu server-存储管理 ubuntu server-存储管理
基本篇 存储 对磁盘的所有操作都要小心小心再小心 磁盘是计算机中最主要的存储设备 传统磁盘分区与逻辑卷管理 事前合理规划很重要 对磁盘的所有操作都要小心小心再小心 磁盘空间管理 df 查看硬盘总体使用情况`bash df
2020-02-09
  目录