精华内容
下载资源
问答
  • 何为后缀表达式 不包含括号,运算符放在两个运算...后缀表达式和中缀表达式的转换 如A+B*(C−D)−E/F 这是怎么搞出来的呢?? 选最靠中的那个优先级最低的符号开始(±),把算数式分为2个部分,若符号数大于二,...

    何为后缀表达式

    不包含括号,运算符放在两个运算对象的后面,所有的计算按运算符出现的顺序,严格从左向右进行(不再考虑运算符的优先规则,如:(2 + 1) * 3 , 即2 1 + 3 *

    很好理解,就是一个符号只对其前面两个数作用

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

    如A+B*(C−D)−E/F

    这是怎么搞出来的呢??

    选最靠中的那个优先级最低的符号开始(±),把算数式分为2个部分,若符号数大于二,树的左儿子是左边的符号,右儿子是右边的符号,若符号不够两个,那么就把数字或字母放在相应的位置。然后又在这两个部分里进行同样的操作。

    然后,树建好之后,对它进行一次后序遍历,将每个节点的值写出即可。

    什么是后序遍历?就是先遍历左子树,再遍历右子树,最后遍历根节点的一种遍历顺序。

    相应的有:

    中序遍历(先遍历左子树,然后访问根结点,最后遍历右子树),可以得到相应的中缀表达式(就是一般算数式)

    前序遍历(先访问根结点然后遍历左子树,最后遍历右子树),前缀表达式(将运算符写在前面,操作数写在后面的表达式,也叫波兰式)

    于是A+B*(C−D)−E/F的后缀表达式就是ABCD-*+EF/-

    前缀表达式就是-+A*B-CD/EF(前缀表达式在不确定中缀表达式的情况下不唯一)

    当中缀表达式和前缀表达式确定时才可以确定后缀表达式,同理,当中缀表达式和后缀表达式确定时才可以确定前缀表达式

    还有一种用栈的方式,直接给链接了:

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

    展开全文
  • 后缀表达式求值 后缀表达式又叫逆波兰表达式,其求值过程可以用到栈来辅助存储。例如要求值的后缀表达式为:1 2 3 + 4 * + 5 - ...1、后缀表达式的操作数与中缀表达式的操作数先后次序相同,而运算符的先后次序不...

    后缀表达式求值

    后缀表达式又叫逆波兰表达式,其求值过程可以用到栈来辅助存储。例如要求值的后缀表达式为:1 2 3 + 4 * + 5 -
    遍历表达式,遇到数字时直接入栈,遇到操作符时,则将栈顶和次栈顶元素出栈与操作符进行运算,然后将结果压如栈中。
    当表达式都遍历完时,此时栈顶元素即为表达式的结果。

    后缀表达式的特点如下:

    1、后缀表达式的操作数与中缀表达式的操作数先后次序相同,而运算符的先后次序不同。
    2、后缀表达式中没有括号,而且运算符没有优先级。
    3、后缀表达式计算过程严格按照从左到右的顺序进行。

    中缀表达式转后缀表达式

    中缀表达式为我们人类能识别的方式,而后缀表达式是计算机进行运算的方式(即我们上述的过程)。

    转换规则

    1)我们使用一个stack栈结构存储操作符,用一个List结构存储后缀表达式结果
    2)首先读取到数字,直接存入list中
    3)当读取到左括号"(“时,直接压栈,当读取到运算符时,分两种情况讨论
    a.当运算符栈为空或者栈顶操作符的优先级小于当前运算符优先级时(如+和-的优先级低于 * 和 /),直接入栈
    b.当运算符栈不为空时且栈顶操作符的优先级大于或等于当前运算符优先级时,循环执行出栈操作并加入list中,直到遇到优先级小于当前运算符的元素为止。循环执行完后再将当前运算符压栈。另外需要注意的是,只有遇到右括号时,左括号才出栈
    4) 当遇到右括号”)"时,循环执行出栈操作并加入到list中,直到遇到左括号为止。并将左括号弹出,但不加入list中
    5) 表达式的值读取完后,将操作符栈中的所有元素弹出并加入到list中

    执行完上面步骤后,list中存储的顺序即为我们转换后的后缀表达式的结果。

    展开全文
  • 前言 由两类对象构成 运算数:如5,6,2,3,4 运算符号:如+,/,-,* 运算符号的优先级不同 计算机处理表达式,它并不能像人一样有逻辑的去判断先处理哪一步,...中缀表达式:5+6/2-34 后缀表达式:562/+34- 这两

    前言

    在这里插入图片描述
    由两类对象构成

    • 运算数:如5,6,2,3,4
    • 运算符号:如+,/,-,*

    运算符号的优先级不同
    计算机处理表达式,它并不能像人一样有逻辑的去判断先处理哪一步,后处理哪一步,它只会严格的按照从左至右执行。
    就像5+6/2 按照计算机的思维 就是 (5+6)/2 这个6 是否拿来做加法运算,按照计算机的思维是不知道的
    所以我们引入了一种表达式,叫做后缀表达式

    后缀表达式

    后缀表达式也叫逆波兰表达式,其求值过程可以用到栈来辅助存储。
    中缀表达式:5+6/2-34
    后缀表达式:562/+34
    -
    这两个表达式是等价的

    后缀表达式计算

    例如562/+34*-
    利用堆栈思想
    在这里插入图片描述
    先将前三个数字压入,之后遇到了运算符号/
    则将 2 和 6 pop 出栈,计算 6/2(后出栈的运算数在运算符之前)得到3,在将 3 push入栈
    此时
    在这里插入图片描述
    后遇到 + 运算符号,则如上 将 3 和 5 pop出栈 进行 5+3=8
    8 push入栈
    之后遇到数字,继续 push 入栈
    此时
    在这里插入图片描述
    遇到运算符,如上的方法进行运算,以此类推,得到值为-4.

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

    对于表达式A+B∗(C−D)−E/F
    从左往右,遇到数字,直接输出
    遇到符号,压入栈中,遇到左括号时我们也将其放入栈中
    如果遇到一个右括号,则将栈元素弹出并输出,将弹出的操作符输出直到遇到左括号为止。
    遇到其他符号,判断其优先级是否比栈顶符号优先级大,若大,则压入,若小或者相同优先级,则pop栈顶符号,直至栈顶符号优先级小于待比较符号

    下面进行操作

    在这里插入图片描述
    下面进行解释:
    1-4操作从左往右。遇到数字输出,遇到符号压栈,第四步,遇到 “*” 乘号优先级比加号高,所以继续入栈

    5-7操作,第五步遇到“(” 将其入栈,后按照顺序,将CD输出,减号 “-” 入栈 第七步遇到右括号,则按照规则,将符号pop出栈,遇到左括号位置,也就是pop出 “-” 号 并输出,并将 “(” 也pop出栈,但不输出。

    第八步操作,遇到符号 “-” 其优先级和 “+”相同,则将 “ + ” pop出兵输出(此处有两个加号 均pop输出) 再将 “ - “ push 入栈

    第九步遇到E直接输出,第十步遇到 " / " 其优先级大于 " - "
    则直接入栈,第十一步,也就是最后一步,F直接输出,表达式已到终点,之后没有其他运算符号,则直接将栈中的符号pop输出出来
    也就是ABCD-*+EF/-

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

    ABC*+DEF+G+
    把后缀表达式逐个元素的压入到栈中,当压入的都是数字,则不采取任何操作,当压入的是运算符,则把运算符下面的两个数字弹出和运算符进行运算,然后把结果继续压入到栈中。
    在这里插入图片描述
    表达式为K2 + K5
    k2 = A + K1 = A + B*C
    K5 = K4 * G = (K3+F) * G=(D * E+F)*G
    K2 + K5 =A + B * C + (D * E + F)*G

    因初学数据结构,若有错误欢迎指出

    展开全文
  • 众所周知啦,我们数学里面的公式就是中缀表达式(infix),形如a*(b+c),支持括号用于调整运算的顺序。我们平常用的就是中缀表达式。...上面就是一个典型的后缀表达式,将它改为中缀表达式其实是(a+b)*((d...

    众所周知啦,我们数学里面的公式就是中缀表达式(infix),形如a*(b+c),支持括号用于调整运算的顺序。我们平常用的就是中缀表达式。

    那么什么是后缀表达式(postfix)?

    后缀表达式(又称为逆波兰reverse polish)就是不需要括号就可以实现调整运算顺序的一种技法。

    比如:ab+cde+**

    上面就是一个典型的后缀表达式,将它改为中缀表达式其实是(a+b)*((d+e)*c)。我们这样将后缀表达式转换成中缀表达式,虽然符合我们的数学计算习惯,但是并不符合计算机运算的方式。我们可以通过数据结构中的栈来理解后缀表达式和它为什么符合计算机计算。

    什么是栈(stack)呢?简单的说就是LIFO(后入先出)。画一张图就是下面这样

     

    堆栈的操作其实很简单,你可以把堆栈想象成一个汉诺塔,你可以在塔顶不断加上汉诺圈,可以从顶部一个一个拿走,但是你不能直接从下面拿走最先放的那个圈。所以你懂了吧,要想拿到最先那个,你必须取出所有的圈,而你最后摆上去的圈可以被立刻拿到。这就是LIFO的本质。

    堆栈的实现方法可以是链表或者数组。它们各有各得优点,它们的对比网络上有很多啦,当然我以后也会写出来。

    现在你知道了栈这种结构就可以重新理解一遍后缀表达式。我们就以 "ab+cde+**" 这个表达式举例。我们创建一个栈,然后从这个表达式开头(当然是从左边)扫描,如果扫描到的是数据就压(push)到栈中。那么在扫描两个字符后栈里情况是这样:

    接着我们发现了一个操作符(operator),是一个加号(+)。对于每个操作符我们进行如下操作:

    1. 从栈中取出两个操作数,比如这里的a,b

    2. 对这两个操作数进行操作符的运算,如这里的a+b

    3. 将操作结果压到栈中,如假设这里的结果m(m=a+b),将m压到栈中

    此时栈中的情况是这样的:

    重复上述的过程,你可以发现后缀表达式实际上计算了中缀表达式的运算式。

    我们会发现当我们扫描到整个后缀表达式的结尾的时候,我们正好计算完整个表达式,因此对于拥有N个字符的后缀表达式,我们计算它的时间是O(N),即为线性时间。

    好了,后缀表达式的运算就是这样的了,现在我们来说一下中缀表达式的运算。

    我们依旧使用(a+b)*(c*(d+e))来举例。对于中缀表达式我们这里采用转换为后缀表达式的方法,依旧使用堆栈来实现计算。

    先介绍一下手写时转换的方法

    对于((a+b)*(c*(d+e)))将其中的操作符提到对应的括号的后面,得到像这样的中间转换式 

                        ((ab)-(c(de)+)*)*

    然后我们把这个中间转换式去掉括号,得到后缀表达式

                        ab-cde+**

    现在我们来实现计算机利用堆栈的转换方式,转换规则如下:

    1. 我们规定+-的优先级为1,*/的优先级为2,( 左括号的优先级为9,) 右括号的优先级为0。

    2. 我们规定只有高优先级的运算符可以压栈,低优先级或者同优先级运算符直接输出。

    3. 我们规定( 压栈后,下一个运算符(右括号除外)均可以压栈。

    4. 我们规定遇到) 后,一直弹出栈内的操作符直到对应的( 出现。

    5. 我们规定操作数均输出,当扫描完成弹出栈中所有元素。

    我们使用图例来直观展示一下:

    上面就是中缀表达式转为后缀表达式的方法了。我们发现转换的时间复杂度也是O(N)。

    接下来我给大家介绍一下一个神奇的数据结构,他可以通过不同遍历方式组合成中辍表达式和后缀表达式。他就是——二叉树!

    二叉树定义:每个节点最多有两个子树的树结构。关于它的知识实在太多,我在这里不一一介绍,大家可以从网上搜集相关资料。

    先给大家看一下二叉树表示我们举例的那个算式:

     

    我们先尝试一下中序遍历,什么是中序遍历?你可以简单的认为是先左,再根,最后右的遍历顺序。注意树结构的思维方式是递归,因此我们从最左边的a开始遍历,遍历顺序依次为a——》+——》b——》*——》c——》*——》d——》+——》e。在遍历的时候你可以认为某一部分是一个整体,这样严格遵循left-parent-right的方式就可以得到中缀表达式了。

    那么最后当然是符合计算机计算的后缀表达式,我们使用后序遍历(先左再右最后根)。遍历顺序是a——》b——》+——》c——》d——》e——》+——》*——》*

    ps:其实通过前序遍历,我们可以得到前缀表达式,不过这玩意真没多大用,爱钻研的各位可以自己搜一下。

    好的,我的思考就到这里了……百尺竿头,今进一步!

    转载于:https://www.cnblogs.com/SmartRabbit/p/4416032.html

    展开全文
  • 有关中缀表达式的计算以及中缀表达式与前缀表达式、后缀表达式之间的转换 后续文章会继续给出 这里只讲前缀表达式与后缀表达式计算的实现方法 前缀表达式   计算方法: 将得到的字符串处理为只含有数字...
  • 数据结构中对栈的应用,典型的例子是后缀表达式和中缀表达式的实现。代码如下:class CCalculator{public: CCalculator(int sz); ~CCalculator(); int Run(); void clean(); private: void AddOperand(int value); ...
  • 利用栈队列实现后缀表达式中缀表达式,win32+vs2013实现
  • 后缀表达式求值 后缀表达式也叫逆波兰表达式,其求值过程可以用到栈来辅助存储。假定待求值的后缀表达式为:6 5 2 3 + 8 * + 3 + *,则其求值过程如下: 1)遍历表达式,遇到的数字首先放入栈中,此时栈如下所示...
  • 前缀表达式,后缀表达式中缀表达式 人看到的是中缀表达式 计算机便于计算的是前缀/后缀表达式 中缀转前缀,两个栈s1,s2,从右往左扫描中缀表达式,遇到符号)则将符号都入栈s1,遇到数字则将数字入栈s2, //当遇到(,...
  • 假定待求值的后缀表达式为:6 5 2 3 + 8 * + 3 + *,则其求值过程如下:1)遍历表达式,遇到的数字首先放入栈中,此时栈如下所示:2)接着读到“+”,则弹出32,执行3+2,计算结果等于5,并将5压入到栈中。...
  • 中缀表达式转换为后缀表达式(Java) 博客说明 文章所涉及的资料来自互联网整理个人总结,意在于个人学习经验汇总,如有什么地方侵权,请联系本人删除,谢谢! 步骤 初始化两个栈:运算符栈 s1 储存中间结果的...
  • 分两种情况:中缀表达式和后缀表达式中缀表达式求值:先将中缀表达式建立二叉树转后缀表达式,然后再求值。 尝试1: #include <iostream> #include <string> #include <...
  • 这个专题很迷,因为这种东西很少使用,一般都是中缀转后缀(容易计算),但是有一些...请你编程求出它的等价中缀表达式。输入输出格式输入格式: 输入文件只有一行,就是后缀表达式。输出格式: 输出文件只有一行,就是
  • 前缀、中缀、后缀表达式是对表达式的不同记法,其区别在于运算符相对于操作数的位置不同,前缀表达式的运算符位于操作数之前,中缀后缀同理 举例: 中缀表达式:1 + (2 + 3) × 4 - 5 前缀表达式:- + 1 × + 2 3 ...
  • 将由数字四则运算符组成的后缀表达式变换为中缀表达式。 输入的后缀表达式包含的运算符不超过15个。 要求转换后的中缀表达式中不应出现不必要的括号。 例如,整个表达式两端的括号要省略,不影响原计算结果的括号...
  • 南故笙烟:中缀表达式转为后缀表达式​zhuanlan.zhihu.com思路分析1.初始化两个栈:运算符栈s1储存中间结果的栈s22.从左至右扫描中缀表达式3.遇到操作数时,将其压入s24.遇到运算符时,比较与s1栈顶运算的优先级*...
  • 算术表达式的前缀表达式,中缀表达式和后缀表达式 这里所谓的前缀,中缀,后缀是根据操作符的位置来定的,如果操作符在操作数前面,则称为前缀表达式,例如“- + 1 × + 2 3 4 5”;如果操作符在操作数之间,则称为...
  • 给定后缀表达式(只限 + - * / 小写字母),求其中缀表达式。 分析 关于表达式的处理,有两种方法,一是单纯的用栈处理,二是先建立一颗表达式树,再对其进行遍历处理。 本文讲述后者的方法 前序遍历 –&...
  • 文章目录背景知识表达式转换问题(考研经典)一:手工转换(1)中缀转前缀和中缀后缀(2)前缀转中缀和后缀转中缀二:用栈实现表达式转换(1)中缀转后缀(2)中缀转前缀 背景知识 中缀表达式:a+b 前缀表达式...
  • 目录: 一:算术表达式的前缀表达式,中缀表达式和后缀表达式 二:前缀、后缀、中缀表达式的计算 一:算术表达式的前缀表达式,中缀表达式和后缀表达式 ...二:前缀、后缀、中缀表达式的计算 ...
  • 操作符操作数的匹配,括号的匹配,(函数参数的个数是否正确等)基本思路如下:用一个链表 List 储存将要生成的后缀表达式用一个栈 Stack 储存操作符判断当前节点, 如果是操作数, 直接加入后缀表达式中, 如果...
  • 思路分析2.1 将数据运算符放入ArrayList2.2 完成后缀表达式的计算三、中缀表达式后缀表达式1. 思路分析2. 代码实现:2.1 将中缀表达式转为对应的List2.2 中缀转后缀的代码实现:总结完整代码: 前言 生活中最...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 2,652
精华内容 1,060
关键字:

后缀表达式和中缀表达式