精华内容
下载资源
问答
  • 目录1、 后缀表达式2、中缀表达式转后缀表达式的详细过程 1、 后缀表达式 后缀表达式又叫逆波兰式,如下: 2+3*5-4*(5-3)的逆波兰式为: 235*+453-*- 逆波兰式的计算过程是: 将字符依次入栈,直到遇到操作符,...

    1、 后缀表达式

    后缀表达式又叫逆波兰式,如下:

          2+3*5-4*(5-3)的逆波兰式为:
          235*+453-*-
    

    逆波兰式的计算过程是:

    将字符依次入栈,直到遇到操作符,遇到操作符后弹出两个字符,计算出结果(并且是上面的那个字符也就是最先出栈的那个字符做减数、除数……而后出栈的那个字符做被减数、被除数……),然后将结果推入栈中,继续遍历后缀表达式,重复前面的操作。
    在这里插入图片描述

    2、中缀表达式转后缀表达式的详细过程

    例如   中缀表达式 a+b*c+(d*e+f)*g
           后缀表达式 abc*+de*f+g*+
    

    中缀表达式转后缀表达式的要求和步骤:

    1、首先要建立一个空栈,这个栈用来存放计算符号(‘+’、‘-’、‘*’、‘/’、‘(’、‘)’),这些符号的优先级是左括号最高,乘除次之、加减最低;然后就可以遍历这个中缀表达式了;
    2、如果当前栈是空的、或者当前元素的优先级高于栈顶元素的优先级、或者栈顶元素是左括号而当前入栈的元素又不是右括号,都直接入栈就可以了;
    3、当前元素是右括号就意味着栈里面肯定有左括号了,那就开始直接输出,直到输出到左括号为止,(不过左括号和右括号本身是不能被输出的(出栈就可以了),右括号的作用就是让左括号及在左括号入栈之后入栈的元素全部输出,但整个过程右括号没有入过一次栈,可以看做就是一种标记吧);
    4、如果当前元素的优先级低于栈顶元素,那么栈顶元素出栈然后输出,继续得到下一个栈顶元素,再与当前元素的优先级比较,如果还是比当前元素的优先级高,继续执行这个操作,否则,当前元素入栈;
    5、整个遍历完之后,将栈中剩下的依次输出最后得到的就是后缀表达式;

    在这里插入图片描述
    代码:地址

    展开全文
  • 一、问题描述 在计算机计算一个算数表达式的时候,首先是将我们熟悉的中缀表达式转化后缀表达式,再基于后缀表达式进行计算得到结果。 中缀表达式: 9+(3-1)*3+10/2,是人所熟悉并常用的表达式形式。 后缀表达式...
    一、问题描述

           在计算机计算一个算数表达式的时候,首先是将我们熟悉的中缀表达式转化后缀表达式,再基于后缀表达式进行计算得到结果。

           中缀表达式: 9+(3-1)*3+10/2,是人所熟悉并常用的表达式形式。

           后缀表达式: 9 3 1 - 3 * + 10 2 / + ,是不包含括号,运算符在两个运算对象后面的表达式,计算机基于对堆栈的处理能够更容易的计算后缀表达式得到结果。

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

          1、首先初始化一个空的字符串(String)和堆栈(Stack)。

          2、将中缀表达式中的数字和运算符(包括加减乘除及左右括号)分割成单个字符存进一个新的数组中,比如上面的中缀表达式就存为:9  +  (  3  -  1  )  *  3  +  10  /  2  。

          3、遍历这个数组,操作数直接放进String中,运算符则存放在堆栈中。

          3.1、如果是空栈,运算符直接进栈。

          3.2、如果栈不为空,将当前遍历到的运算符与栈顶运算符做优先级比较,如果栈顶运算符为左括号或优先级低于当前运算符,则当前运算符入栈,否则栈顶运算符弹出栈并连接在String后,当前运算符再与弹栈后的栈顶运算符做比较,直到栈顶运算符低于当前运算符的优先级或遇到左括号,将当前运算符入栈当前运算符若是右括号,则将栈顶运算符依次弹出并依次连接到String后,直到遇到左括号,并将左括号弹出(但是不连接在String后的,注意后缀表达式中是没有括号的)。

          4、如果中缀表达式遍历完毕后栈中还有运算符则将栈中剩下的运算符依次弹出并连接在String后,最终得到的字符串String就是后缀表达式。

    三、计算后缀表达式

          1、初始化一个栈用来存放操作数,然后定义一个变量存放最后的结果。

          2、遍历后缀表达式,遍历到操作数则依次进栈,遍历到运算符的时候将栈顶操作数弹出(假设赋给变量a),再弹出一个栈顶操作数(假设赋给变量b),用后者对前者做该运算符对应的运算(假设遍历到的运算符为+,则做计算b+a),然后将计算结果入栈

          3、以此类推,最终遍历得到的结果即为运算结果。

    四、python代码
    # 中缀表达式
    infix_expression = '9+(3-1)*3+10/2'
    
    # 优先级列表
    priority1 = ['*', '/']
    priority2 = ['+', '-']
    # 字符是否使用列表
    useable = [True for i in range(len(infix_expression))]
    # 初始化堆栈和后缀表达式
    stack = []
    postfix_expression = []
    for i in range(len(infix_expression)):
        # 防止操作数字符重复使用
        if useable[i] is True:
            # 操作数字符直接加入堆栈
            if infix_expression[i].isdigit():
                operand = [infix_expression[i]]
                if i < len(infix_expression) - 1:
                    j = 1
                    # 将长度大于1的操作数作为整体加入堆栈
                    while (infix_expression[i + j].isdigit() or infix_expression[i + j] is '.'):
                        operand.append(infix_expression[i + j])
                        useable[i + j] = False
                        j += 1
                        if (i + j) == len(infix_expression):
                            break
                operand = "".join(operand)
                postfix_expression.append(operand)
            else:
                # 堆栈列表不为空
                if len(stack):
                    # '('直接加入堆栈
                    if infix_expression[i] is '(':
                        stack.append(infix_expression[i])
                    # 处理处于优先级1的运算符
                    elif infix_expression[i] in priority1:
                        while(True):
                            if len(stack) == 0 or stack[-1] in priority2 or stack[-1] is '(':
                                stack.append(infix_expression[i])
                                break
                            else:
                                postfix_expression.append(stack.pop())
                    # 处理处于优先级2的运算符
                    elif infix_expression[i] in priority2:
                        while (True):
                            if len(stack) == 0 or stack[-1] is '(':
                                stack.append(infix_expression[i])
                                break
                            else:
                                postfix_expression.append(stack.pop())
                    # 处理')'
                    elif infix_expression[i] is ')':
                        while(stack[-1] != '('):
                            postfix_expression.append(stack.pop())
                        stack.pop()
                # 堆栈列表为空,直接加入堆栈
                else:
                    stack.append(infix_expression[i])
    # 获得最终的后缀表达式
    for i in range(len(stack)):
        postfix_expression.append(stack.pop())
    # 利用后缀表达式计算结果
    for i in range(len(postfix_expression)):
        if postfix_expression[i].isdigit():
            stack.append(postfix_expression[i])
        else:
            oper1 = float(stack.pop())
            oper2 = float(stack.pop())
            if postfix_expression[i] == '+':
                stack.append(oper2 + oper1)
            elif postfix_expression[i] == '-':
                stack.append(oper2 - oper1)
            elif postfix_expression[i] == '*':
                stack.append(oper2 * oper1)
            elif postfix_expression[i] == '/':
                stack.append(oper2 / oper1)
    print('中缀表达式;', infix_expression)
    print('后缀表达式:', " ".join(postfix_expression))
    print('计算结果:', stack[0])

    代码运行结果:



    展开全文
  • 本文主要写了有关前缀中缀后缀表达式的堆栈,入栈、出栈的方式和表达式求解的计算机求值原理,一般我们的思维是中缀表达式

    数据结构和算法(9)中缀 前缀 后缀表达式

    前缀表达式(波兰表达式)

    1)前缀表达式又称波兰式,前缀表达式的运算符位于操作数之前

    2)例如:(2+4)*5-6对应的前缀表达式就是- * + 3 4 5 6

    前缀表达式计算机求值原理

    1.从右到左扫描表达式,遇到数字,将数字压入堆栈,遇到运算符,弹出栈顶的两个数,用运算符对他们做相应的计算(栈顶元素和次顶元素),并将结果入栈。

    2.重复上述过程,知道表达式最左端,最后运算得出的值即为表达式的结果。

    例如:(3+4)*5-6对应的前缀表达式是3 4 + 5 * 6 -,针对前缀缀表达式求值步骤如下:

    1)从右至左扫描,将6、5、4、3压入堆栈

    2)遇到+运算符 ,因此弹出3和4(3为栈顶元素,4位次顶元素),计算出3+4的值,得7,再将7入栈

    3)接下来是 * 运算符,因此弹出7和5,计算出7*5=35,将35入栈

    4)最后是-运算符,计算出35-6的值,即29,由此得出最终结果

    中缀表达式

    1)中缀表达式就是常见的运算表达式,如(3+4)*5-6

    2)中缀表达式的求值使我们最熟悉的,但是对计算机来说却不好操作,因此,在计算结果时,我们往往会将中缀表达式转换成其他表达式来操作(一般转成后缀表达式。)

    后缀表达式

    1)后缀表达式又叫逆波兰表达式,与前缀表达式相似,只是运算符位于操作数之后,

    2)中缀表达式举例说明:(3+4)*5-6对应的后缀表达式就是3 4 + 5 * 6 -

    正常的表达式 逆波兰表达式
    a+b a b +
    a+(b-c) a b c - +
    a+(b-c)*d a b c - d * +
    a+d*(b-c)+ a d b c - * +
    a=1+3 a 1 3 + =

    后缀表达式的计算机求值原理

    1.从左至右扫描表达式,遇到数字时,将数字压入堆栈,遇到运算符时,弹出栈顶的两个数,用运算符对它们做相应的计算,(栈顶元素和次顶元素),并将结果入栈;

    2.重复上述过程直到表达式最右端,最后运算出的值,即为表达式的结果

    例如:(3+4)*5-6对应的后缀表达式是3 4 + 5 * 6 -,针对后缀表达式求值步骤如下:

    1)从左至右扫描,将3和4压入堆栈

    2)遇到+运算符,因此弹出4和3(4位栈顶元素,3位次顶元素),计算出3+4的值,得7;再将7入栈;

    3)将5入栈

    4)接下来是 * 运算符,因此弹出5和7,计算出7*5=35,将35入栈

    5)将6入栈

    6)最后是 - 运算符,计算出35-6的值,即29,由此得出最终结果

    展开全文
  • 下边是例子忘了以后帮助理解:

    下边是例子忘了以后帮助理解:

    展开全文
  • 后缀表达式是计算机容易运算的表达式,运算符在运算数后面,从左到右进行运算,无需考虑优先级,运算呈线性结构. 先举个简单的转换例子 2+9/3-5 (前缀)-> 2 9 3 / + 5 - (后缀) 先进行乘除再进行加减 运算规律,.....
  • #include #include int lookahead;void error(){printf("synatax error\n");exit(1);}void match(int t){if(lookahead==t)lookahead=getchar();elseerror();}void term(){if(isdigit(lookahead)){putchar(lookahead)...
  • 原理不赘述,随便找个博客看看后缀表达式即其计算 原理简单,实现起来有几个小问题: Q1:A+B*C的后缀变表达式为ABC*+,当ABC为具体的1、2、3时,后缀表达式为123*+, 123怎么理解,1和2和3还是12和3还是1和23... ...
  • 栈及其应用-中缀表达式转后缀表达式并用后缀表达式求值 一:栈的基本原理 栈是一种特殊的线性表,因为它对线性表中的元素做出了明确的要求:栈中的元素只能从线性表的一端进出,且要遵循“先入后出”的原则,即先进栈...
  • 后缀表达式又成为逆波兰表达式,在sicp里面有讲过,简单的加减乘除可以用栈很快写出来,但是要用到括号,幂运算等就要整理出符号的优先级,根据优先级的比较决定是否进行入栈。 ps.先占个坑#include #include #...
  • 在计算一个表达式的时候,可以用数据结构中栈的知识,将我们平常熟悉的中缀表达式转为后缀表达式,再将后缀表达式进行计算得到结果。先说下什么是中缀什么是后缀: 中缀表达式:eg: 9+(3-1)*3+10/2,就是我们平常...
  • 前缀_中缀_后缀表达式栈的前缀_中缀_后缀表达式三种表达式转换方法前缀、后缀表达式原理的计算器求值中缀转后缀表达式代码实现思路代码实现后缀表达式实现简易整数计算器思想代码实现 栈的前缀_中缀_后缀表达式 三种...
  • 逆波兰表达式又叫做后缀表达式。这个知识点在数据结构和编译原理这两门课程中都有介绍,下面是一些例子:    正常的表达式 逆波兰表达式    a+b ---> a,b,+    a+(b-c) ---> a,b,c,-,+    a+(b-c)d --...
  • 编译原理实验一中缀表达式转后缀表达式
  • 在计算一个表达式的时候,可以用数据结构中栈的知识,将我们平常熟悉的中缀表达式转为后缀表达式,再将后缀表达式进行计算得到结果。先说下什么是中缀什么是后缀: 中缀表达式:eg: 9+(3-1)*3+10/2,就是我们平常...
  • 0.1) 本文旨在总结 中缀表达式转后缀表达式并计算后缀表达式的值 的步骤,并给出源代码实现; 0.2) 本文中涉及到的源代码均为原创,是对中缀转后缀和计算后缀的简单实现,(旨在理清它的原理),故源代码中 考虑的...
  • 用java实现编译原理后缀表达式实验,包括词法,语法分析,还有输入错误恢复等。。
  • 本文使用实现了MATLAB实现中缀表达式转后缀表达式并计算(数字包含0-9,符号包含+-*、())后缀表达式得到结果,下面是原理和代码。代码可以在CSDN中下载。
  • 逆波兰表达式又叫做后缀表达式。这个知识点在数据结构和编译原理这两门课程中都有介绍,下面是一些例子:正常的表达式 逆波兰表达式a+b ---> a,b,+a+(b-c) ---> a,b,c,-,+a+(b-c)d ---> a,d,b,c,-,,+a=1+3 ...
  • 要求用户输入的后缀表达式每个字符之间以空格隔开 去除用户输入的后缀表达式中的空格,变成一个只含有数字和符号的列表 :return: 整理之后的列表 """ method_list = ['+', '-', '*', '/'] eq_str = input('请...
  • 中缀表达式转后缀表达式 规则:从左到右遍历中缀表达式的每个数字和符号,如果是数字直接写出(即成为后缀表达式的一部分);若是符号,则判断与栈顶符号的优先级,若是右括号或低于栈顶符号优先级(当是右括号时候...
  • 后缀表达式

    2013-08-20 10:41:40
    表达式的表示形式有中缀、前缀和后缀3中形式。中缀表达式按操作符的优先级进行计算(后面代码实现只包括+、-、*、\,小括号),...由后缀表达式计算中缀表达式原理:计算机处理后缀表达式求值问题是比较方便的,即将遇到
  • 原理就是在将中缀表达式转换为后缀表达式的时候将“()”以及不同优先级的运算符,按照优先级顺序进行逐次排列,从而使得后缀表达式可以更方便进行计算。由上述可知,转换的过程,就是对运算符进行排序的过程。...
  • 主要介绍了Java中缀表达式转后缀表达式实现方法,结合实例形式分析了Java中缀表达式转换成后缀表达式的相关算法原理与具体实现技巧,需要的朋友可以参考下
  • 先写词法分析的源文件,用正则表达式表示出需要识别的字符,例如数字,乘法,加法和括号,如果识别到其他非法字符需要报错,用flex生成lex.yy.c文件。语法分析用LR方法进行语法分析,LR方法需要先根据文法构造自动机...
  • 中缀表达式即普通的运算式子,运算符是以中缀形式处于操作数...可以用这种原理即输入普通式子(即中缀表达式),转换成后缀表达式,然后通过后缀表达式(逆波兰式)的计算,可以得出结果。 1 #include <stdio.h&g...
  • 利用栈的原理,把中缀表达式转为后缀表达式(C++)。
  • 前缀表达式与后缀表达式

    千次阅读 2015-06-14 14:38:39
    前缀表达式与后缀表达式都可以由中缀表达式来转换而成,由于在转化的过程中已经考虑了优先级,所以前缀表达式和后缀表达式的求值直接借助栈就可以,不再有优先级的规则。中缀表达式转换为前缀表达式和后缀表达式都...
  • 后缀表达式Postfix

    2010-05-16 18:12:10
    后缀表达式Postfix,将输入的一个中缀表达式转化为后缀表达式输出,有助于编译原理语法分析的学习

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 450
精华内容 180
关键字:

后缀表达式原理