首页
学习
活动
专区
工具
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 ^ ^ / +

参考链接

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

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

相关·内容

利用栈转换中缀表达式后缀表达式

本篇是栈篇最后一篇,记录一下如何用栈实现中缀表达式后缀表达式。...先举例一个后缀表达式9 3 1 - 2 * + 5 2 / + 他中缀表达式是9+(3-1)*2+5/2 首先我们要找到这个表达式优先级优先级最高是括号 其次是乘法和除法再然后是加法 那么如何用栈来演示呢...*B+C,先入栈*,然后到下一个操作符判断和栈顶优先级,很明显+号小于栈顶*号,所以我们已经找到了最右操作数B,然后就可以在操作数列表里加入操作符了(后置),直接把栈顶元素pop字符串列表里,然后再把当前操作符...push,等待遍历其右操作数。...,我们会用 string fix;存放我们新后缀表达式,接着根据传入表达式长度进入循环,如果是数字的话就加到字符串后面,如果是操作符的话,首先要看栈顶元素,如果栈不为空,而且当前操作符大于栈顶元素符号满足的话

21310
  • Python——中缀后缀转换(Sta

    tokenList = infixexpr.split()     for token in tokenList:         # 这里用到是string模块两个方法,源代码都是手敲字母和数字...1、传入参数,这里用复杂一点 ? 2、 实例化、创建最终生成后缀样式 列表、将传入字符串分隔开 ?...3、当token==“(”时,opstack存入“(”,因为转换成后缀就不需要用“()”表示优先级,存起来是用于做优先级判断 ?...21、传入“)”,取出opstack“ + ”并返回到postfixList,接着删掉对应“(” ?...22、tokenList列表遍历完跳出for循环,接下来就是一次取出opstack“ * ”和“ - ”并添加到postfixList,再按规定格式返回结果 ? 23、我们答案在此 ?

    1.6K20

    应用中缀后缀表达式

    后缀表达式,由波兰科学家在20世纪50年代提出,将运算符放在数字后面,更便于计算机去计算,而我们平常看到 1 + 2、5 * 10 等,都是中缀表达式,这种方式,符合人类思考方式。...举几个例子: 5 + 4 => 5 4 + 1 + 2 * 3 => 1 2 3 * + 8 + ( 3 – 1 ) * 5 => 8 3 1 – 5 * + 左侧为中缀表达式,右侧为后缀表达式。...那这种转换规则和方法是什么呢?...首先我们来看一下规则: 【后缀表达式转换规则】 对于数字:直接输出 对于符号: 左括号:进栈 运算符号:与栈顶符号进行优先级比较 若栈顶符号优先级低:此符号进栈 (默认栈顶若是左括号,左括号优先级最低)...LinkStack_Pop(stack); } // 下标++ i++; } while (LinkStack_Size(stack)) { // 输出栈内容 output((char)(int)LinkStack_Pop

    17020

    应用中缀表达式转换为后缀表达式后缀表达式计算

    中缀表达式转换为后缀表达式 后缀表达式 做数学运算时,经常使用中缀表达式,即“操作数 运算符 操作数”。在计算机处理时候更习惯后缀表达式,即“操作数 操作数 运算符”。...例如a + b * c转换为后缀表达式a b c * +,使用栈可以将中缀表达式转换为后缀表达式,具体方法为: 扫描到数字直接输出 扫描到运算符则与栈顶比较,若扫描到运算符优先级低于或等于栈顶运算符优先级...,则弹栈直到栈空或栈顶运算符优先级低于扫描到运算符,之后运算符入栈;否则直接入栈。...base_stack.New_link_stack() topost := To_postfix{} topost.data_stack = link return &topost } 后缀表达式计算...计算方法 后缀表达式计算比较简单,顺序扫描整个后缀表达式: 若遇到数字,直接入栈 若遇到运算符,弹栈两次取出两个数字,按运算符运算,将结果再次入栈 这样扫描完整个后缀表达式之后,栈中就应该只有一个数

    1.5K70

    中缀表达式转换为后缀表达式(栈使用)

    中缀表达式如1*2+(2-1), 其运算符一般出现在操作数之间, 因此称为中缀表达式,也就是大家编程表达 式。...为达到上述目的, 就要将中缀表达式进行改写,变为后缀表达式 如上面的表达式 1*2+(2-1), 就变为12*21-+; 后缀表达式不含有括号, 且后缀表达式操作数和中缀表达式操作数排列次序完全相同...我们实现时候,只需要用一个特定工作方式数据结构(栈),就可以实现。 其中stack op;用来存放运算符栈。数组ans用来存放后缀表达式。...否则的话,就依次把栈运算符弹出加到数组ans末尾,直到遇到优先级低于扫描 运算符或栈空,并且把扫描到运算符压入栈。 就这样依次扫描,知道结束为止。...如果扫描结束,栈还有元素,则依次弹出加到数组ans末尾,就得到了后缀表达式

    40410

    应用----算术表达式计算问题(中缀后缀后缀计算)

    应用----算术表达式计算问题(中缀后缀后缀计算) 问题引入:算术表达式计算是编译系统一个基本问题,其实现方法是堆栈一个典型应用。任何一个算术表达式都是由操作数、运算符和分界符组成。...算术表达式计算分为两步: 中缀表达式转为后缀表达式 后缀表达式计算。...一、中缀表达式后缀表达式 1.基本运算规则: 先乘除后加减 先括号内后括号外 同级别先左后右 2.算法如下: 设置一个堆栈,初始时将栈顶元素置为"#"....,并把该运算结果作为一个新操作数入栈,此过程一直进行后缀算术表达式读完,最后栈顶操作数就是改后缀算数表达式运算结果。...0; } 四、运行结果(就用上面的2+(3-4*5)测试) 可以看到,上述分析过程和结果都正确,其实熟悉编译原理同学可以直接用“移进”和“规约动作”实现中缀算数表达式后缀算数表达式转换。

    1K20

    中缀表达式后缀表达式方法,步骤和原理及后缀表达式运算方式

    中缀后缀 本文大部分资料参考慕课何钦铭老师数据结构 相关慕课链接:表达式求值 中缀表达式是最常用算术表达式,运算符在运算数中间,运算需要考虑运算符优先级....后缀表达式是计算机容易运算表达式,运算符在运算数后面,从左到右进行运算,无需考虑优先级,运算呈线性结构....先举个简单转换例子 2+9/3-5 (前缀)-> 2 9 3 / + 5 – (后缀) 先进行乘除再进行加减 运算规律,运算数位置不变,改变是运算符位置 可以推栈实现,用堆栈储存等待运算符...再来解释一下开始简单例子 带括号运算 选取慕课里何钦铭老师案例 后缀表达式运算步骤: (以堆栈储存) 从左到右,遇到运算符就弹出相应运算数,运算后再把结果入栈.最终结果就是栈顶数值...这篇文章只是整理中缀表达式后缀表达式方法和理论,目的是为了理解. 具体代码实现看我另一篇文章(模拟表达式运算). 这部分转换对于初学者来说可能很模糊,建议去看开头链接那个视频.

    40620

    C++ 使用栈求解中缀后缀表达式

    为了简化问题,本文只限于讨论基于常量操作数和双目运算符表达式。 在计算机表达式描述可以有以下 3 种: 后缀表达式:操作数,操作数,运算符。 中缀表达式:操作数,运算符,操作数。...如果比optStack栈顶运算符优先级低,则弹出运算符,再从numStack栈中弹出 2 个操作数,对其进行运算,且把运算结果压入numStack栈。...中缀后缀表达式 虽然后缀表达式计算过程要比中缀表达式简单很多,前提条件是要先把中缀表达式转换成后缀表达式。 转换流程: 初始化一个运算符栈。...4.2 编码实现 中缀表达式后缀表达式实现过程类似于中缀表达式求值过程,只是不需要进行计算。或者说中缀表达式求值过程包括了中缀表达式转换成后缀表达式以及对后缀表达式求值过程。...总结 本文讲解了中缀后缀表达式求值过程以及如何将一个中缀表达式转换成后缀表达式

    84400

    【数据结构】后缀(逆波兰)表达式计算以及中缀后缀方法

    对于从来没有接触过后缀表达式同学来讲,这样表述是很难受。不过你不喜欢,有机器喜欢,比如我们聪明计算机。 二、中缀表达式后缀表达式 1....传统方法 我们把平时所用标准四则运算表达式,即“9+(3-1)×3+10÷2”叫做中缀表达式。因为所有的运算符号都在两数字中间,现在我们问题就是中缀后缀转化。...规则: 从左到右遍历中缀表达式每个数字和符号 若是数字就输出,即成为后缀表达式一部分; 若是符号,则判断其与栈顶符号优先级,是右括号或优先级低于栈顶符号(乘除优先加减)则栈顶元素依次出栈并输出...也就是说,前 6 张图栈底“+”是指中缀表达式开头 9 后面那个“+”,而图 2-1-4 左图中栈底(也是栈顶)“+”是指“9+(3-1)×3+”最后一个“+”。...从刚才推导你会发现,要想让计算机具有处理我们通常标准(中缀表达式能力,最重要就是两步: 将中缀表达式转化为后缀表达式(栈用来进出运算符号)。

    17410

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

    我们可以一起来了解一下: 结合题目中给测试用例给大家解释一下: 我们正常写表达式,就比如题目中这个:(2 + 1) * 3 这种写法叫做中缀算术表达式,即运算符写在操作数中间,但是这种写法计算机是不能直接计算...所以呢,这里就需要我们做一件事情,就是把它变成后缀表达式,其实就是根据优先级对表达式运算符排一个序,并且放到对应操作数后面。...中缀表达式后缀表达式 那现在大家再来思考一个问题: 如果给我们一个中缀表达式,我们如何把它转换成对应后缀表达式? 分析 那中缀后缀呢,也是需要借助一个栈,具体怎么做呢?...比如现在有这样一个中缀表达式1+2*3-4 怎么把它转成后缀呢?...中缀表达式求值 那大家再来思考一下,如果给一个中缀表达式,我们该如何求它值呢? ,是不是就是上面两种操作结合啊。

    10810

    借助栈来实现单链表逆置运算_中缀后缀表达式互相转换

    大家好,又见面了,我是你们朋友全栈君。 原题链接 算术表达式有前缀表示法、中缀表示法和后缀表示法等形式。日常使用算术表达式是采用中缀表示法,即二元运算符位于两个运算数中间。...请设计程序将中缀表达式转换为后缀表达式。 输入格式: 输入在一行给出不含空格中缀表达式,可包含+、-、*、\以及左右括号(),表达式不超过20个字符。...输出格式: 在一行输出转换后后缀表达式,要求不同对象(运算数、运算符号)之间以空格分隔,但结尾不得有多余空格。...输入样例: 2+3*(7-4)+8/4 输出样例: 2 3 7 4 - * + 8 4 / + 注意 数字前面有正负号和小数情况 #include #define x

    32820

    动画:BM 算法坏字符规则与好后缀规则

    BM 算法中有两个核心规则,本文主要介绍这两个规则。 定义 BM算法 一个特点是当不匹配时候 一次性可以跳过不止一个字符 。即它不需要对被搜索字符串字符进行逐一比较,而会跳过其中某些部分。...坏字符规则(bad-character shift):当文本串某个字符跟模式串某个字符不匹配时,我们称文本串这个失配字符为坏字符,此时模式串需要向右移动,移动位数 = 坏字符在模式串位置...好后缀规则(good-suffix shift):当字符失配时,后移位数 = 好后缀在模式串位置 - 好后缀在模式串上一次出现位置,且如果好后缀在模式串没有再次出现,则为 -1。...好后缀针对是模式串。 ? 坏字符规则 坏字符出现时候有两种情况进行讨论。 1、模式串没有出现了文本串那个坏字符,将模式串直接整体对齐这个字符后方,继续比较。 ? ?...好后缀规则 1、如果模式串存在已经匹配成功后缀,则把目标串与好后缀对齐,然后从模式串最尾元素开始往前匹配。 ? ?

    1.7K20

    计算器——可支持小数任意四则运算(中缀表达式转为后缀表达式算法)

    中缀表达式转为后缀表达式原理过程主要包括以下步骤: 1. 初始化两个栈,一个用于存储操作数,一个用于存储运算符。 2. 从左到右扫描中缀表达式每个字符。 3....如果遇到运算符,则分两种情况处理:如果运算符优先级大于等于栈顶运算符优先级,则将栈顶运算符弹出并压入后缀表达式,直到栈为空或者栈顶运算符优先级低于当前运算符为止,然后将当前运算符压入栈;如果运算符优先级小于栈顶运算符优先级...当表达式扫描完毕后,如果栈仍有剩余运算符,则将这些运算符依次弹出并压入后缀表达式。 6. 最后,后缀表达式剩余元素即为转换后结果。         ...,用于从输入流读取一行文本并存储字符串对象。...getline(cin, expression); //程序会提示用户输入一行文本,然后使用getline()函数读取输入文本并存储expression字符串,最后输出读取到文本。

    12010

    表达式(四则运算)计算算法

    编译系统中缀形式算术表达式处理方式是: 先把中缀表达式转换成后缀表达式,再进行计算。 后缀表达式就是表达式运算符出现在操作数后面,并且不含括号,如AB+C*。...基于后缀表达式两个特点,计算过程如下:计算时只要从左到右依次扫描后缀表达式各个单词,当读到单词为运算符时,就对该运算他会前两个操作数进施以此运算所代表操作,然后将结果T插入后缀表达式再重复上面的操作...(2).顺序读入中缀表达式,当读到单词为操作数时将其加入线性表L, 并接着读下一个单词。...为+或-,x2为*或/时,优先级x1<x2,满足中缀表达式规则1.先乘除后加减;x1为+、-、*或/,x2为(或/时,优先级x1<x2,满足中缀表达式规则2.先括号内后括号外;当x1运算符x2运算符同级别时...出现表$表示中缀表达式语法出错。

    3.1K10

    golang 计算器实现

    注意,由于前缀、中缀后缀表达式(以后可能略掉“表达式”三字)只不过是表达式不同写法,所以任一中缀表达式必然存在效果、意义相同前缀、后缀表达式(类似于用不同语言表达同一意思,如who are you...,其实过程是“固定”: 1.遍历中缀表达式 2.如果当前中缀元素为操作数,则直接将此操作数“输出”后缀表达式尾端 3.如果当前中缀元素为'*','/'或'(',直接push入操作符栈 4.如果当前中缀元素为...')',则依次pop出栈顶操作符,“输出”后缀表达式尾端,直至pop得到是一个'('才停止,并丢弃该'(' 5.如果当前中缀元素为'+'或'-',则依次pop出栈顶操作符、“输出”后缀表达式尾端...6.如果当前中缀元素为'=',则依次pop出栈顶操作符、“输出”后缀表达式尾端,直至栈底(栈空)。   ...,其用途说明在Calculator.h void translate() { //遍历中缀表达式数组,将其中存储中缀表达式转换为后缀表达式并存入后缀表达式数组 //i为中缀表达式数组

    80420

    算数四则混合运算表达式求值

    字符转换成数字(包括解析小数) 主要思路: 算术表达式有三种类型:前缀,中缀后缀表达式,而这里主要利用中缀后缀表达式 示图: 中缀表达式:运算符位于操作数中间 中缀表达式运算规则...没有括号,只有操作数和运算符 我们平常使用中缀表达式,而后缀表达式运算优先已经好了,所以我们用后缀表达式进行四则计算 步骤一:中缀表达式后缀表达式 示图: 过程实现...: 遍历中缀表达式 遇到数字直接放入后缀表达式 遇到左括号入栈 遇到右括号则将栈里运算符一直出栈左括号出栈,并按出栈顺序放入后缀表达式(达到一个去括号效果) 遇到 *...遇到其他字符则直接报错退出程序 当遍历完后再将栈剩余运算符给出栈并放入后缀表达式 步骤二:依靠后缀表达式计算结果 因为后缀表达式已经达到去括号,决定运算符优先级效果了,所以可以直接计算...遍历结束后,栈顶数据就是最后结果 思考: 优先级:后缀表达式已经将运算符优先级给处理好了 字符转浮点:从中缀表达式后缀时,遍历数字或小数点则一直进行放入后缀表达式,并在最后放一个空格做分隔符

    80210

    数据结构与算法-(7)---栈应用-(3)表达式转换

    ,而且在嵌套括号,内层优先级更高这样(A+B)*C就是A与B和再乘以C 全括号表达式与前后缀表达式关系 虽然人们已经习惯了这种表示法,但计算机处理最好是能明确规定所有的计算顺序,这样无需处理复杂优先规则...C将变为前缀"+A*BC"后缀"ABC*+"为了帮助理解,子表达式加了下划线 在前缀和后缀表达式,操作符次序完全决定了运算次序,不再有混淆 所以在很多情况下,表达式在计算机表示都避免使用复杂中缀形式...通用中缀后缀算法⭐ 在中缀表达式转换为后缀形式处理过程,操作符比操作数要晚输出 所以在扫描到对应第二个操作数之前,需要把操作符先保存起来 而这些暂存操作符,由于优先级规则还有可能要反转次序输出...”表达式后缀表达式操作符应该出现在左括号对应右括号位置 所以遇到左括号,要标记下,其后出现操作符优先级提升了,一旦扫描到对应右括号,就可以马上输出这个操作符 总结: 在从左到右扫描逐个字符扫描中缀表达式过程...利用中缀后缀操作流程 后面的算法描述,约定中缀表达式是由空格隔开一系列单词(token)构成, 操作符单词包括*/+-() 而操作数单词则是单字母标识符A、B、C等。

    14110

    Java数据结构和算法(六)——前缀、中缀后缀表达式

    以及数据结构与本篇博客主题前缀、中缀后缀表达式有什么关系呢? 1、人如何解析算术表达式   如何解析算术表达式?...请大家先看看什么是前缀表达式中缀表达式后缀表达式:这三种表达式其实就是算术表达式三种写法,以 3+4-5为例   ①、前缀表达式:操作符在操作数前面,比如 +-543   ②、中缀表达式:操作符在操作数中间...,计算机容易识别的是前缀表达式后缀表达式,将中缀表达式转换为前缀表达式或者后缀表达式之后,计算机能很快计算出表达式值,那么中缀表达式是如何转换为前缀表达式后缀表达式,以及计算机是如何解析前缀表达式后缀表达式来得到结果呢...3、后缀表达式   后缀表达式,指的是不包含括号,运算符放在两个运算对象后面,所有的计算按运算符出现顺序,严格从左向右进行(不再考虑运算符优先规则)。   ...既然后缀表达式这么好,那么问题来了:   ①、如何将中缀表达式转换为后缀表达式?   对于这个问题,转换规则如下: ?

    1.7K90
    领券