首页
学习
活动
专区
工具
TVP
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往

中缀到后缀表达式中的关联性规则

中缀表达式到后缀表达式的转换是编译原理中的一个重要概念,主要用于将人类可读的中缀表达式转换为计算机可高效处理的后缀表达式(也称为逆波兰表示法)。这个转换过程涉及到几个关键的关联性规则:

基础概念

  1. 中缀表达式:常见的数学表达式形式,例如 3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3
  2. 后缀表达式:操作符位于操作数之后的表达式形式,例如 3 4 2 * 1 5 - 2 3 ^ ^ / +

关联性规则

  1. 操作符优先级:定义了操作符之间的优先级关系,例如乘法和除法的优先级高于加法和减法。
  2. 结合性:定义了相同优先级的操作符是从左到右还是从右到左进行计算。大多数操作符是左结合的,例如 +-,而幂运算 ^ 是右结合的。

转换过程

  1. 初始化一个空栈用于存放操作符和括号。
  2. 初始化一个空列表用于生成后缀表达式。
  3. 从左到右扫描中缀表达式
    • 如果遇到操作数,直接添加到后缀表达式列表中。
    • 如果遇到左括号 (,压入栈中。
    • 如果遇到右括号 ),则弹出栈顶元素并添加到后缀表达式列表中,直到遇到左括号 (
    • 如果遇到操作符,比较其与栈顶操作符的优先级:
      • 如果栈为空或栈顶为左括号 (,或当前操作符的优先级高于栈顶操作符,则将当前操作符压入栈中。
      • 否则,弹出栈顶操作符并添加到后缀表达式列表中,重复此步骤。
  • 将栈中剩余的操作符依次弹出并添加到后缀表达式列表中

应用场景

  • 编译器设计:用于表达式求值和语法分析。
  • 计算器:实现数学表达式的计算。
  • 算法设计:在图论、数据结构等领域中,后缀表达式常用于实现高效的算法。

示例

假设我们有中缀表达式 3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3,转换过程如下:

  1. 扫描到 3,添加到后缀表达式列表:3
  2. 扫描到 +,压入栈中。
  3. 扫描到 4,添加到后缀表达式列表:3 4
  4. 扫描到 *,压入栈中。
  5. 扫描到 2,添加到后缀表达式列表:3 4 2
  6. 扫描到 /,压入栈中。
  7. 扫描到 (,压入栈中。
  8. 扫描到 1,添加到后缀表达式列表:3 4 2 / 1
  9. 扫描到 -,压入栈中。
  10. 扫描到 5,添加到后缀表达式列表:3 4 2 / 1 5
  11. 扫描到 ),弹出栈顶元素 - 并添加到后缀表达式列表:3 4 2 / 1 5 -
  12. 弹出栈顶元素 / 并添加到后缀表达式列表:3 4 2 1 5 - /
  13. 扫描到 ^,压入栈中。
  14. 扫描到 2,添加到后缀表达式列表:3 4 2 1 5 - / 2
  15. 扫描到 ^,压入栈中。
  16. 扫描到 3,添加到后缀表达式列表:3 4 2 1 5 - / 2 3
  17. 弹出栈顶元素 ^ 并添加到后缀表达式列表:3 4 2 1 5 - / 2 3 ^
  18. 弹出栈顶元素 ^ 并添加到后缀表达式列表:3 4 2 1 5 - / 2 3 ^ ^
  19. 弹出栈顶元素 + 并添加到后缀表达式列表:3 4 2 1 5 - / 2 3 ^ ^ +

最终得到的后缀表达式为:3 4 2 * 1 5 - 2 3 ^ ^ / +

参考链接

通过上述过程,可以将复杂的中缀表达式转换为计算机可高效处理的后缀表达式,从而实现更高效的计算和表达式求值。

页面内容是否对你有帮助?
有帮助
没帮助

相关·内容

  • 栈在表达式求值中的应用——逆波兰表达式求值+中缀表达式转后缀表达式

    我们正常写的表达式,就比如题目中的这个:(2 + 1) * 3 这种写法叫做中缀算术表达式,即运算符写在操作数的中间,但是这种写法计算机是不能直接计算的,因为涉及运算符优先级的问题,比如1+2*3,应该先算*。 所以呢,这里就需要我们做一件事情,就是把它变成后缀表达式,其实就是根据优先级对表达式中的运算符排一个序,并且放到对应的操作数后面。 就比如题目中给的这个示例:((2 + 1) * 3)这个表达式对应的后缀表达式就是["2","1","+","3","*"](题中是把它放到一个字符串数组中了)。 即1和2先进行后面的+,得到的结果再和3进行后面的*,得到最终结果。这样就直接从前往后算,不用考虑优先级的问题了。

    01

    中缀表达式转换为后缀表达式(逆波兰表达式)并对其求值

    中缀表达式转后缀表达式思路: 1.初始化一个运算符栈s1和存储中间结果的List集合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中的元素,结果即为中缀表达式对应的后缀表达式。

    03
    领券