美文网首页data structure and algorithms
前缀中缀和后缀表达式

前缀中缀和后缀表达式

作者: spraysss | 来源:发表于2019-10-20 13:28 被阅读0次

中缀

人类正常使用的计算表达式即为中缀表达式比如:( 1 + 2 ) * 3 - 4

前缀

前缀表达式的计算逻辑为从右至左扫描,遇到数字入栈,遇到操作符,弹出两个数字运算然后将结果入栈,重复以上过程直到表达式最左端,最后运算得出的值即为表达式的结果
( 1 + 2 ) * 3 - 4的前缀表达式为 - * + 1 2 3 4

后缀

( 1 + 2 ) * 3 - 4的后缀1 2 + 3 * 4 -
后缀表达式的计算逻辑为从左至右扫描,遇到数字入栈,遇到操作符,弹出两个数字运算然后将结果入栈,重复以上过程直到表达式最右端,最后运算得出的值即为表达式的结果

中缀表达式转后缀表达式算法

  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中的元素并输出,结果的逆序即为中缀表达式对应的后缀表达式

简单的来说就是:

  • 碰到操作数直接入s2
  • 碰到操作符的优先级比栈顶元素高的话就需要入栈,否则就从s1中弹出操作符,压入s2,并继续上述过程,最后该操作符肯定是要入栈的

相关文章

  • 前缀,中缀,后缀表达式

    全文转载自:前缀、中缀、后缀表达式(逆波兰表达式),侵删。 前缀表达式,中缀表达式,后缀表达式都是四则运算的表达方...

  • 7.19-经典难问题总结

    1. 前缀,后缀和中缀之间相互转换 中缀表示转前缀/后缀(附代码)针对负数的情况前缀/中缀/后缀相互转换 2. T...

  • 算术表达式之前缀、中缀、后缀表达式转化

    概述 前缀、中缀、后缀表达式一般是根据操作符的位置来确定的,在我们去理解什么是前缀表达式和后缀表达式之前,可以先看...

  • 数据结构笔记(线性结构->堆栈)

    前缀表达式 -+abc/de中缀表达式 a+bc-d/e后缀表达式 abc*+de/- 堆栈(stack):...

  • 栈-表达式转换(手算)

    1.中缀表达式 -> 前缀表达式 先加括号,然后从左往右依次把运算符放到括号前面 2.中缀表达式 -> 后缀表达式...

  • 前缀中缀和后缀表达式

    中缀 人类正常使用的计算表达式即为中缀表达式比如:( 1 + 2 ) * 3 - 4 前缀 前缀表达式的计算逻辑为...

  • 表达式转换

    算术表达式有前缀表示法、中缀表示法和后缀表示法等形式。日常使用的算术表达式是采用中缀表示法,即二元运算符位于两个运...

  • 算法面经--前、中、后缀表达式的规则与转换

    前、中、后缀表达式的规则与转换 一、基本介绍 前缀、中缀、后缀表达式是对表达式的不同记法,其区别在于运算符相对于操...

  • 中缀表达式转后缀表达式并求值

    1.什么是中缀表达式?中缀表达式示例 2.什么是后缀表达式?后缀表达式示例 3.代码

  • 表达式树

    表达式树中缀表达式转换为后缀表达式后缀表达式总结

网友评论

    本文标题:前缀中缀和后缀表达式

    本文链接:https://www.haomeiwen.com/subject/oboomctx.html