精华内容
下载资源
问答
  • 文章目录前缀表达式(波兰表达式)前缀表达式分析与介绍思路分析中缀表达式中缀表达式分析与介绍后缀表达式(逆波兰表达式)后缀表达式分析与介绍思路分析逆波兰计算器代码实现逆波兰计算器中缀表达式转换为后缀...
  • 数据结构学习:前缀中缀后缀表达式转化 中缀转后缀的手算方法: ① 确定中缀表达式中各个运算符的运算顺序 ② 选择下一个运算符,按照「左操作数 右操作数 运算符」的方式组合成一个新的操作数 ③ 如果还有运算符没...

    数据结构学习:前缀中缀后缀表达式转化

    中缀转后缀的手算方法:
    ① 确定中缀表达式中各个运算符的运算顺序
    ② 选择下一个运算符,按照「左操作数 右操作数 运算符」的方式组合成一个新的操作数
    ③ 如果还有运算符没被处理,就继续 ②
    在这里插入图片描述

    由于运算顺序不唯一,因此对应的后缀表达式也不唯一
    “左优先”原则:只要左边的运算符能先计算,就优先算左边的

    后缀表达式的手算方法:
    从左往右扫描,每遇到一个运算符,就让运算符前面最近的两个操作数执行对应运算,合体为一个操作数
    在这里插入图片描述

    用栈实现后缀表达式的计算:
    ①从左往右扫描下一个元素,直到处理完所有元素
    ②若扫描到操作数则压入栈,并回到①;否则执行③
    ③若扫描到运算符,则弹出两个栈顶元素,执行相应运算,运算结果压回栈顶,回到①

    注意:先出栈的是“右操作数”
    在这里插入图片描述

    栈里的大致情况为:
    在这里插入图片描述
    在这里插入图片描述在这里插入图片描述

    中缀转前缀的手算方法:
    ① 确定中缀表达式中各个运算符的运算顺序
    ② 选择下一个运算符,按照「运算符 左操作数 右操作数」的方式组合成一个新的操作数
    ③ 如果还有运算符没被处理,就继续 ②
    (从右往左算,从右往左看)
    在这里插入图片描述

    “右优先”原则:只要右边的运算符能先计算,就优先算右边的。

    用栈实现前缀表达式的计算:
    ①从右往左扫描下一个元素,直到处理完所有元素
    ②若扫描到操作数则压入栈,并回到①;否则执行③
    ③若扫描到运算符,则弹出两个栈顶元素,执行相应运算,运算结果压回栈顶,回到①

    在这里插入图片描述

    中缀表达式转后缀表达式(机算)

    初始化一个栈,用于保存暂时还不能确定运算顺序的运算符。
    从左到右处理各个元素,直到末尾。可能遇到三种情况:
    ① 遇到操作数。直接加入后缀表达式。
    ② 遇到界限符。遇到“(”直接入栈;遇到“)”则依次弹出栈内运算符并加入后缀表达式,直到弹出“(”为止。注意:“(”不加入后缀表达式。
    ③ 遇到运算符。依次弹出栈中优先级高于或等于当前运算符的所有运算符,并加入后缀表达式,若碰到“(” 或栈空则停止。之后再把当前运算符入栈。
    按上述方法处理完所有字符后,将栈中剩余运算符依次弹出,并加入后缀表达式。

    Eg:
    A + B - C * D / E + F
    步骤:
    1.遇到操作数A。直接加入后缀表达式:A
    2.遇到运算符+,压入栈底,栈底为:+
    3.遇到操作数B。直接加入后缀表达式:A B,栈底为:+
    4.遇到运算符-,依次弹出栈中优先级高于或等于-的所有运算符,即弹出+,并把运算符-压入栈,后缀表达式:A B +,栈底为-
    5.遇到操作数C。直接加入后缀表达式:A B + C
    6.遇到运算符*,栈里没有优先级高于的运算符,不弹出栈,把压入栈,栈:栈底为-,栈顶为*,后缀表达式:A B + C
    在这里插入图片描述

    7.遇到操作数D。直接加入后缀表达式:A B + C D
    8.遇到运算符/,依次弹出栈中优先级高于或等于/的所有运算符,即弹出*,把/压入栈,栈:栈底为-,栈顶为/,后缀表达式:A B + C D *
    9.遇到操作数E。直接加入后缀表达式:A B + C D * E
    在这里插入图片描述

    10.遇到运算符+,依次弹出栈中优先级高于或等于+的所有运算符,即弹出/ 与- ,把+压入栈,栈:栈底为+,后缀表达式:A B + C D * E / -
    11.遇到操作数F。直接加入后缀表达式:A B + C D * E / - F
    12.处理完所有字符,将栈中剩余运算符+依次弹出,并加入后缀表达式:A B + C D * E / - F +

    Eg:
    A + B * (C - D) – E / F
    步骤
    1.遇到操作数A。直接加入后缀表达式:A
    2.遇到运算符+,压入栈底,栈底为:+
    3.遇到操作数B。直接加入后缀表达式:A B,栈底为:+
    4.遇到运算符*,栈里没有优先级高于的运算符,不弹出栈,把压入栈,栈:栈底为+,栈顶为*,后缀表达式:A B
    5.遇到界限符(,把(压入栈,栈:栈底为+,栈中间为*,栈顶为(,后缀表达式:A B
    6.遇到操作数C。直接加入后缀表达式:A B C,栈:栈底为+,栈中间为*,栈顶为(
    在这里插入图片描述

    7.遇到运算符-,压入栈,前面为(,不弹出栈内元素
    在这里插入图片描述

    8.遇到操作数D。直接加入后缀表达式:A B C D
    9.遇到界限符),弹出-(,运算法-加入到后缀表达式中,而界限符 ( 不加入后缀表达式
    在这里插入图片描述

    10.遇到运算符 - ,把栈里优先级高于-的运算法弹出
    在这里插入图片描述

    11.遇到操作数D。直接加入后缀表达式:A B C D - * + E
    12.遇到运算符/,压入栈
    13.遇到操作数F。直接加入后缀表达式:A B C D - * + E F
    在这里插入图片描述

    14…处理完所有字符,将栈中剩余运算符依次弹出,后缀表达式:A B C D - * + E F / -

    后缀表达式的计算(机算)
    用栈实现后缀表达式的计算:
    ①从左往右扫描下一个元素,直到处理完所有元素
    ②若扫描到操作数则压入栈,并回到①;否则执行③
    ③若扫描到运算符,则弹出两个栈顶元素,执行相应运算,运算结果压回栈顶,回到①

    中缀表达式的计算(用栈实现)

    用栈实现中缀表达式的计算:
    初始化两个栈,操作数栈和运算符栈
    若扫描到操作数,压入操作数栈
    若扫描到运算符或界限符,则按照“中缀转后缀”相同的逻辑压入运算符栈(期间也会弹出运算符,每当弹出一个运算符时,就需要再弹出两个操作数栈的栈顶元素并执行相应运算,运算结果再压回操作数栈)

    函数调用的特点:最后被调用的函数最先执行结束(LIFO)

    函数调用时,需要用一个“函数调用栈” 存储:
    ① 调用返回地址
    ② 实参
    ③ 局部变量

    递归调用时,函数调用栈可称为“递归工作栈”
    每进入一层递归,就将递归调用所需信息压入栈顶
    每退出一层递归,就从栈顶弹出相应信息

    缺点:效率低,太多层递归可能会导致栈溢出;可能包含很多重复计算

    展开全文
  • 前缀表达式 1 前缀表达式又称波兰式,前缀表达式的运算符位于操作数之前。 2 举例 (3+4)×5-6 对应的前缀表达式是: - × + 3 4 5 6 3前缀表达式的计算机求值过程 从右至左扫描表达式,遇到数字时,将数字压...

    一 前缀表达式

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

    2 举例

     (3+4)×5-6 对应的前缀表达式是: - × + 3 4 5 6

    3 前缀表达式的计算机求值过程

    从右至左扫描表达式,遇到数字时,将数字压入堆栈,遇到运算符时,弹出栈顶的两个数,用运算符对它们做相应的计算(栈顶元素 和 次顶元素),并将结果入栈;重复上述过程直到表达式最左端,最后运算得出的值即为表达式的结果。

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

    第一步:从右至左扫描,将6、5、4、3压入堆栈

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

    第三步:接下来是×运算符,因此弹出7和5,计算出7×5=35,将35入栈。

    第四步:最后是-运算符,计算出35-6的值,即29,由此得出最终结果。

    二 中缀表达式

    中缀表达式注意下面两点。

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

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

    三 后缀表达式 

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

    2 后缀表达式举例

    (3+4)×5-6 对应的后缀表达式就是 3 4 + 5 × 6 –

    3  后缀表达式的计算机求值

    从左至右扫描表达式,遇到数字时,将数字压入堆栈,遇到运算符时,弹出栈顶的两个数,用运算符对它们做相应的计算(次顶元素 和 栈顶元素),并将结果入栈;重复上述过程直到表达式最右端,最后运算得出的值即为表达式的结果。

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

    第一步:从左至右扫描,将3和4压入堆栈。

    第二步:遇到+运算符,弹出4和3(4为栈顶元素,3为次顶元素),计算出3+4的值,得7,再将7入栈。

    第三步:将5入栈。

    第四步:接下来是×运算符,弹出5和7,计算出7×5=35,将35入栈。

    第五步:将6入栈。

    第六步:最后是-运算符,计算出35-6的值,即29,由此得出最终结果。

    四 中缀表达式转后缀表达式

    后缀表达式适合计算机进行运算,但是人却不太容易写出来,尤其是表达式很长的情况下,因此在开发中,我们需要将中缀表达式转成后缀表达式。

    中缀表达式转后缀表达式具体步骤如下:

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

    举例说明

    将中缀表达式“1+((2+3)×4)-5”转换为后缀表达式的过程如下

    结果为"1 2 3 + 4 × + 5 –"

     

     

     

    展开全文
  • 前缀表达式(波兰表达式) 前缀表达式又称波兰式,前缀表达式的运算符位于操作数之前 举例说明: (3+4)×5-6 对应的前缀表达式就是 - × + 3 4 5 6 前缀表达式求值 前缀表达式的计算机求值 从右至左扫描表达式,遇到...

    原文在这里

    表达式

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

    1. 前缀表达式又称波兰式,前缀表达式的运算符位于操作数之前
    2. 举例说明: (3+4)×5-6 对应的前缀表达式就是 - × + 3 4 5 6

    前缀表达式求值

    前缀表达式的计算机求值

    从右至左扫描表达式,遇到数字时,将数字压入堆栈,遇到运算符时,弹出栈顶的两个数,用运算符对它们做相应的计算(栈顶元素 和 次顶元素),并将结果入栈;重复上述过程直到表达式最左端,最后运算得出的值即为表达式的结果

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

    • 从右至左扫描,将6、5、4、3压入堆栈
    • 遇到+运算符,因此弹出34(3为栈顶元素,4为次顶元素),计算出3+4的值,得7,再将7入栈
    • 接下来是×运算符,因此弹出75,计算出7×5=35,将35入栈
    • 最后是-运算符,计算出35-6的值,即29,由此得出最终结果

    中缀表达式

    中缀表达式

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

    中缀表达式的求值是我们人最熟悉的,但是对计算机来说却不好操作(前面我们讲的案例就能看的这个问题),因此,在计算结果时,往往会将中缀表达式转成其它表达式来操作(一般转成后缀表达式.)

    中缀表达式对于我们人来好搞,计算机他算不算明白,就离谱

    计算机不知道怎么算这个优先级

    后缀表达式(逆波兰表达式)

    后缀表达式

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

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

    再比如:

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

    后缀表达式的计算机求值

    从左至右扫描表达式,遇到数字时,将数字压入堆栈,遇到运算符时,弹出栈顶的两个数,用运算符对它们做相应的计算(次顶元素 和 栈顶元素),并将结果入栈;重复上述过程直到表达式最右端,最后运算得出的值即为表达式的结果

    例如: (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,由此得出最终结果

    我们完成一个逆波兰计算器,要求完成如下任务:

    1. 输入一个逆波兰表达式(后缀表达式),使用栈(Stack), 计算其结果
    2. 支持小括号和多位数整数,因为这里我们主要讲的是数据结构,因此计算器进行简化,只支持对整数的计算。
    3. 思路分析
    4. 代码完成
    package com.atguigu.stack;
    
    /**
     * ClassName:  <br/>
     * Description:  <br/>
     * Date: 2021-02-20 14:27 <br/>
     * @project data_algorithm
     * @package com.atguigu.stack
     */
    
    import java.util.ArrayList;
    import java.util.List;
    import java.util.Stack;
    
    public class PolandNotation {
    
    
    }
    //编写一个类 Operation 可以返回一个运算符 对应的优先级
    class Operation {
        private static int ADD = 1;
        private static int SUB = 1;
        private static int MUL = 2;
        private static int DIV = 2;
    
        //写一个方法,返回对应的优先级数字
        public static int getValue(String operation) {
            int result = 0;
            switch (operation) {
            case "+":
                result = ADD;
                break;
            case "-":
                result = SUB;
                break;
            case "*":
                result = MUL;
                break;
            case "/":
                result = DIV;
                break;
            default:
                System.out.println("不存在该运算符" + operation);
                break;
            }
            return result;
        }
    
    }
    //完成对逆波兰表达式的运算
    /*
     * 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,由此得出最终结果
     */
    
    public static int calculate(List<String> ls) {
        // 创建给栈, 只需要一个栈即可
        Stack<String> stack = new Stack<String>();
        // 遍历 ls
        for (String item : ls) {
            // 这里使用正则表达式来取出数
            if (item.matches("\\d+")) { // 匹配的是多位数
                // 入栈
                stack.push(item);
            } else {
                // pop出两个数,并运算, 再入栈
                int num2 = Integer.parseInt(stack.pop());
                int num1 = Integer.parseInt(stack.pop());
                int res = 0;
                if (item.equals("+")) {
                    res = num1 + num2;
                } else if (item.equals("-")) {
                    res = num1 - num2;
                } else if (item.equals("*")) {
                    res = num1 * num2;
                } else if (item.equals("/")) {
                    res = num1 / num2;
                } else {
                    throw new RuntimeException("运算符有误");
                }
                //把res 入栈
                stack.push("" + res);
            }
    
        }
        //最后留在stack中的数据是运算结果
        return Integer.parseInt(stack.pop());
    }
    //将一个逆波兰表达式, 依次将数据和运算符 放入到 ArrayList中
    public static List<String> getListString(String suffixExpression) {
        //将 suffixExpression 分割
        String[] split = suffixExpression.split(" ");
        List<String> list = new ArrayList<String>();
        for(String ele: split) {
            list.add(ele);
        }
        return list;
    
    }
    //方法:将 中缀表达式转成对应的List
    //  s="1+((2+3)×4)-5";
    public static List<String> toInfixExpressionList(String s) {
        //定义一个List,存放中缀表达式 对应的内容
        List<String> ls = new ArrayList<String>();
        int i = 0; //这时是一个指针,用于遍历 中缀表达式字符串
        String str; // 对多位数的拼接
        char c; // 每遍历到一个字符,就放入到c
        do {
            //如果c是一个非数字,我需要加入到ls
            if((c=s.charAt(i)) < 48 ||  (c=s.charAt(i)) > 57) {
                ls.add("" + c);
                i++; //i需要后移
            } else { //如果是一个数,需要考虑多位数
                str = ""; //先将str 置成"" '0'[48]->'9'[57]
                while(i < s.length() && (c=s.charAt(i)) >= 48 && (c=s.charAt(i)) <= 57) {
                    str += c;//拼接
                    i++;
                }
                ls.add(str);
            }
        }while(i < s.length());
        return ls;//返回
    }
    //即 ArrayList [1,+,(,(,2,+,3,),*,4,),-,5]  =》 ArrayList [1,2,3,+,4,*,+,5,–]
    //方法:将得到的中缀表达式对应的List => 后缀表达式对应的List
    public static List<String> parseSuffixExpreesionList(List<String> ls) {
        //定义两个栈
        Stack<String> s1 = new Stack<String>(); // 符号栈
        //说明:因为s2 这个栈,在整个转换过程中,没有pop操作,而且后面我们还需要逆序输出
        //因此比较麻烦,这里我们就不用 Stack<String> 直接使用 List<String> s2
        //Stack<String> s2 = new Stack<String>(); // 储存中间结果的栈s2
        List<String> s2 = new ArrayList<String>(); // 储存中间结果的Lists2
    
        //遍历ls
        for(String item: ls) {
            //如果是一个数,加入s2
            if(item.matches("\\d+")) {
                s2.add(item);
            } else if (item.equals("(")) {
                s1.push(item);
            } else if (item.equals(")")) {
                //如果是右括号“)”,则依次弹出s1栈顶的运算符,并压入s2,直到遇到左括号为止,此时将这一对括号丢弃
                while(!s1.peek().equals("(")) {
                    s2.add(s1.pop());
                }
                s1.pop();//!!! 将 ( 弹出 s1栈, 消除小括号
            } else {
                //当item的优先级小于等于s1栈顶运算符, 将s1栈顶的运算符弹出并加入到s2中,再次转到(4.1)与s1中新的栈顶运算符相比较
                //问题:我们缺少一个比较优先级高低的方法
                while(s1.size() != 0 && Operation.getValue(s1.peek()) >= Operation.getValue(item) ) {
                    s2.add(s1.pop());
                }
                //还需要将item压入栈
                s1.push(item);
            }
        }
    
        //将s1中剩余的运算符依次弹出并加入s2
        while(s1.size() != 0) {
            s2.add(s1.pop());
        }
    
        return s2; //注意因为是存放到List, 因此按顺序输出就是对应的后缀表达式对应的List
    
    }
    

    执行

    public static void main(String[] args) {
    
    
        //完成将一个中缀表达式转成后缀表达式的功能
        //说明
        //1. 1+((2+3)×4)-5 => 转成  1 2 3 + 4 × + 5 –
        //2. 因为直接对str 进行操作,不方便,因此 先将  "1+((2+3)×4)-5" =》 中缀的表达式对应的List
        //   即 "1+((2+3)×4)-5" => ArrayList [1,+,(,(,2,+,3,),*,4,),-,5]
        //3. 将得到的中缀表达式对应的List => 后缀表达式对应的List
        //   即 ArrayList [1,+,(,(,2,+,3,),*,4,),-,5]  =》 ArrayList [1,2,3,+,4,*,+,5,–]
    
        String expression = "1+((2+3)*4)-5";//注意表达式
        List<String> infixExpressionList = toInfixExpressionList(expression);
        System.out.println("中缀表达式对应的List=" + infixExpressionList); // ArrayList [1,+,(,(,2,+,3,),*,4,),-,5]
        List<String> suffixExpreesionList = parseSuffixExpreesionList(infixExpressionList);
        System.out.println("后缀表达式对应的List" + suffixExpreesionList); //ArrayList [1,2,3,+,4,*,+,5,–]
    
        System.out.printf("expression=%d", calculate(suffixExpreesionList)); // ?
    
    
    
        /*
    
        //先定义给逆波兰表达式
        //(30+4)×5-6  => 30 4 + 5 × 6 - => 164
        // 4 * 5 - 8 + 60 + 8 / 2 => 4 5 * 8 - 60 + 8 2 / +
        //测试
        //说明为了方便,逆波兰表达式 的数字和符号使用空格隔开
        //String suffixExpression = "30 4 + 5 * 6 -";
        String suffixExpression = "4 5 * 8 - 60 + 8 2 / +"; // 76
        //思路
        //1. 先将 "3 4 + 5 × 6 - " => 放到ArrayList中
        //2. 将 ArrayList 传递给一个方法,遍历 ArrayList 配合栈 完成计算
    
        List<String> list = getListString(suffixExpression);
        System.out.println("rpnList=" + list);
        int res = calculate(list);
        System.out.println("计算的结果是=" + res);
    
        */
    }
    

    原文在这里

    展开全文
  • 1. 前缀, 中缀, 后缀表达式 1.1. 前缀表达式(波兰表达式) 1.1.1. 前缀表达式的定义 1.1.2. 前缀表达式的求值步骤 1.1.3. 前缀表达式的计算示例 1.2. 中缀表达式 1.2.1. 中缀表达式的定义 1.3. 后缀表达式 1.3.1. ...
     
     
    

    博主的 Github 地址


    1. 前缀, 中缀, 后缀表达式

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

    1.1.1. 前缀表达式的定义

    • 前缀表达式又称波兰式, 前缀表达式的运算符位于操作数之前
    • 转换:
      表达式 (3+4)*5-6 的前缀表达式就是 - * + 3 4 5 6

    1.1.2. 前缀表达式的求值步骤

    • 注意: 扫描的是前缀表达式, 因此扫描前要将原表达式进行转换
    1. 从右到左扫描表达式
    2. 遇到数字时, 将数字压入堆栈
    3. 遇到运算符时, 弹出栈顶的两个数,
      用运算符对它们做相应的计算, 并将结果入栈
    4. 重复上述过程知道表达式最左端,
      最后运算得出的值为表达式的结果

    1.1.3. 前缀表达式的计算示例

    1. 表达式 (3+4)*5-6 转换成前缀表达式 - * + 3 4 5 6

    2. 从右到左扫描前缀表达式, 按顺序将 6 5 4 3 压入栈中

    3. 数字全部入栈后, 遇到 "+" 运算符, 栈中 3 和 4 出栈,
      并计算 3 + 4 的结果, 得到 7 并将其入栈.

    4. 然后下一个扫到 "*" 运算符, 栈中继续出栈 2 个元素,
      并计算 7 * 5 的结果, 得到 35 同时将其入栈.

    5. 最后扫到 "-" 运算符, 计算出 35 - 6 的结果,
      将 29 压入栈中, 得出最后结果, 并输出.


    1.2. 中缀表达式

    1.2.1. 中缀表达式的定义

    • 中缀表达式就是常见的运算表达式, 如表达式 (3+4)*5-6
    • 中缀表达式求值对于人类来说是最合理的, 但对于计算机并不好操作.
    • 在计算机中进行计算时, 通常都会将中缀表达式转换成其他表达式来操作,
      一般来说都是转换成后缀表达式.

    1.3. 后缀表达式

    1.3.1. 后缀表达式的定义

    • 后缀表达式又称逆波兰表达式, 与前缀表达式类似, 只是运算符位于操作数之后

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

    • 更多的例子:

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

    1.3.2. 后缀表达式计算流程

    • 注意: 同样需要将中缀表达式转换后缀表达式后操作
    1. 从左到右扫描表达式
    2. 遇到数字时, 将数字压入堆栈
    3. 遇到运算符时, 弹出栈顶的两个数,
      用运算符对它们做计算, 并将结果入栈.
    4. 重复上述过程直到表达式最右端,
      最后得到的运算结果就是表达式的最终结果.

    1.3.3. 后缀表达式计算实例

    1. 表达式 (3+4)*5-6 转换成后缀表达式 3 4 + 5 * 6 -
    2. 从左到右进行扫描, 将 3 4 压入栈中
    3. 遇到 "+" 运算符, 因此弹出 4 和 3,
      并计算 3 + 4 的值, 得到结果为 7 同时将其压入栈
    4. 将 5 进行入栈
    5. 然后遇到 "*" 运算符, 因此出栈 7 和 5,
      计算 7 * 5 得到结果为 35 并将其入栈
    6. 将 6 进行入栈
    7. 最后是 "-" 运算符, 计算出 35 - 6 的值,
      得到最终结果 29, 并将其入栈.
    展开全文
  • 虽然人的大脑很容易理解与分析中缀表达式,但对计算机来说中缀表达式却是很复杂的,因此计算表达式的值时,通常需要先将中缀表达式转换为前缀后缀表达式,然后再进行求值。对计算机来说,计算前缀后缀表达式的值...
  • 文章目录1 相关概念2 与二叉树关系3 表达式转换 1 相关概念 前缀表达式(Prefix ...后缀表达式(Postfix Notation)与之相反,是指运算符写在操作数后面的不包含括号的算术表达式,也叫做逆波兰表达式 中缀表达式(...
  • 35,15,+,80,70,-,*,20,/ //后缀表达方式(((35+15)*(80-70))/20)=25 //中缀表达方式 /,*,+,35,15,-,80,70, 20 //前缀表达方式 人的思维方式很容易固定!正如习惯拉10进制。就对2,3,4,8,16等进制不知所措...
  • 前缀中缀后缀表达式

    2017-08-16 12:05:04
    它们都是对表达式的记法,因此也被称为前缀记法、中缀记法和后缀记法。它们之间的区别在于运算符相对与操作数...3 4 + 5 × 6 - 后缀表达式 中缀表达式(中缀记法) 中缀表达式是一种通用的算术或逻辑公式表示方法
  • 7.5 前缀中缀后缀表达式(逆波兰表达式) 7.5.1 前缀表达式(波兰表达式) 前缀表达式又称波兰表达式,前缀表达式的运算符位于操作数之前 举例说明:(3 + 4) X 5 - 6 对应的前缀表达式就是 - X + 3 4 5 6 ...
  • 前缀中缀后缀表达式及其互相转换

    万次阅读 2015-05-24 19:59:02
    计算机中前缀中缀后缀表达式是数据结构栈的重要应用,他们都是对表达式的记法,只是相对位置不一样,顾名思义,前缀表达式指的是符号都在操作数之前,中缀表达式指的是运算符都在操作数之后,而后缀表达式是之后。...
  • 中缀后缀表达式

    2018-02-23 16:40:12
    前缀表达式(例:+ 3 4)或后缀表达式(例:3 4 +)相比,中缀表达式不容易被计算机解析,但仍被许多程序语言使用,因为它符合人们的普遍用法。 与前缀或后缀记法不同的是,中缀记法中括号是必需的。计算过程中...
  • 表达式2*(9+6/3-5)+4,称为中缀表达式,表示成2 9 6 3 / + 5 - * 4 +称为后缀表达式,表示成+ * 2 - + 9 / 6 3 5 4称为前缀表达式。 ·基本要求 将中缀表达式,转换为后缀表达式前缀表达式,再分别计算转换后的...
  • 利用STL中stack,解析前、后缀表达式,并将中缀表达式转换到相应的前、后缀表达式
  • 第二步:对二叉树进行前序遍历,得到前缀表达式,对二叉树进行后序遍历,得到后缀表达式。 第一步:中序表达式转为二叉树 在上篇文章栈结构与四则运算中提到了通过算术表达式构造二叉树,比如9+(3-1)*3+10/2是一...
  • 后缀表达式: 对应着后序遍历 例子:A = B / (C+D) * E - F 转换成二叉树如下图:(由底部网上画,也就是C+D开始) 中序遍历结果为:A=B/ C+D*E-F对应着 中序表达式 为:A=B/ C+D*E-F 前序遍历...
  • 4.2 前缀中缀后缀表达式前言基于三种表达式特点的定义定义示例解释基于二叉树定义 前言       我第一次接触这三种表达式是在数据结构课程的二叉树遍历部分,所以下面大部分是从...
  • 后缀表达式(又称逆波兰表达式),后缀表达式的特点就是:每一运算符都置于其运算对象之后,以上面的中缀表达式1+23为例子,转为后缀表达式就是123+ 下面先分析怎么把中缀表达式转换为后缀表达式,这里我们考虑六种...
  • 前缀表达式:不含括号的算术表达式,而且是将运算符写在前面,操作数写在后面的表达式。求法:首先从右往左扫描表达式,从右边第一个字符判断,如果当前字符是数字,则一直到字符串的末尾再记录下来;如果是运算符,...
  • 前缀表达式(波兰表达式前缀表达式又称波兰表达式前缀表达式的运算符位于操作数之前 举例说明:(3+4)*5-6对应的前缀表达式就是 - * + 3 4 5 6 前缀表达式的计算 ...
  • 1、中缀表达式转后缀表达式的两种方法: 假定有中缀表达式A:1 + (( 2 + 3)* 4 ) – 5,请将它转化为后缀表达式。 方法一:直接转换法 (1)首先确定表达式表达式A的运算顺序,然后加括号:((1 + (( 2 + 3)* 4 ))...
  • 一、中缀表达式转换为前缀后缀表达式给个中缀表达式:a+b*c-(d+e)首先根据运算符的优先级给所有运算单位加括号:((a+(b*c))-(d+e))将运算符号移动到对应括号的前面然后去掉所有括号就转换为前缀表达式:-( +(a *...
  • 前缀_中缀_后缀表达式栈的前缀_中缀_后缀表达式三种表达式转换方法前缀后缀表达式原理的计算器求值中缀后缀表达式代码实现思路代码实现后缀表达式实现简易整数计算器思想代码实现 栈的前缀_中缀_后缀表达式 三种...
  • 前缀表达式(例:+ 3 4)或后缀表达式(例:3 4 +)相比,中缀表达式不容易被计算机解析,但仍被许多程序语言使用,因为它符合人们的普遍用法。 与前缀或后缀记法不同的是,中缀记法中括号是必需的。计算过程中...
  • 中缀表达式转前缀后缀表达式

    千次阅读 2020-09-24 14:46:16
    中缀表达式转前缀后缀表达式

空空如也

空空如也

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

前缀中缀后缀表达式