后缀表达式 订阅
逆波兰式(Reverse Polish notation,RPN,或逆波兰记法),也叫后缀表达式(将运算符写在操作数之后) 展开全文
逆波兰式(Reverse Polish notation,RPN,或逆波兰记法),也叫后缀表达式(将运算符写在操作数之后)
信息
又    称
后缀表达式
使用方式
将运算符写在操作数之后
中文名
逆波兰式
外文名
Reverse Polish notation,RPN
逆波兰式定义
一个表达式E的后缀形式可以如下定义:(1)如果E是一个变量或常量,则E的后缀式是E本身。(2)如果E是E1 op E2形式的表达式,这里op是任何二元操作符,则E的后缀式为E1'E2' op,这里E1'和E2'分别为E1和E2的后缀式。(3)如果E是(E1)形式的表达式,则E1的后缀式就是E的后缀式。如:我们平时写a+b,这是中缀表达式,写成后缀表达式就是:ab+(a+b)*c-(a+b)/e的后缀表达式为:(a+b)*c-(a+b)/e→((a+b)*c)((a+b)/e)-→((a+b)c*)((a+b)e/)-→(ab+c*)(ab+e/)-→ab+c*ab+e/-
收起全文
精华内容
下载资源
问答
  • 2022-03-14 12:01:18

    示例:中缀表达式:1 + ( ( 2 + 3 )× 4) - 5 =》后缀表达式:1 2 3 + 4 * + 5 -

    思路:

    1. 创建两个栈,运算符栈s1 和 数值栈s2。

    2. 从左到右扫描中缀表达式。

    3. 遇到数的话直接假如到数栈s2中

    4. 遇到运算符的话,分为以下几种情况:

      1) 如果s1为空,或者s1的栈顶为左括号 ” (“ 就直接将运算符入栈

      2)如果s1不为空,扫描到的运算符的优先级高于栈顶运算符的优先级的话,也直接入栈

      3)如果s1不为空,扫描到的运算符的优先级小于或等于栈顶运算符的优先级的话,就将s1中的运算符弹出并压入到s2栈中,然后再转到(4.1)与s1中新的栈顶的运算符进行比较。

    5. 遇到括号的情况:

      1)当遇到左括号时,直接入栈

      2)当遇到右括号时,将s1栈中的符号依次弹出并压入到s2中,直到遇见左括号为止。然后将这一对括号丢弃

      6.重复2-5的步骤,直到扫描到表达式的最右边(即表达式最后)

      7.将s1中剩余的运算符依次弹出,并压入到s2中

      8.依次弹出s2中的元素并输出,此时的结果的逆序就是我们要的后缀表达式

    后缀表达式的计算:

    思路:

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

    例如: (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 入栈;

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

    代码:

    package com.lzh.stack;
    
    import java.util.ArrayList;
    import java.util.List;
    import java.util.Stack;
    
    /**
     * 逆波兰表达式的计算
     */
    public class ReversePolandNotation {
        public static void main(String[] args) {
            //定义一个String变量,来接收后缀表达式
            String suffixExpression = "3 4 + 5 * 6 - ";
            //String suffixExpression = "3#4#+#5#x#6#-#";
            String expression = "1+((2+3)*4)-5";//注意表达式(这是一个中缀表达式)
            /**
             * 思路:
             * 1.创建一个ArrayList集合
             * 2.把表达式中的每个字符串分割出来,放到集合中
             * 3.然后把集合传到一个方法中,然后让这个方法进行表达式的计算即可
             */
            List<String> list = getList(suffixExpression);
            int res = calculate(list);
            System.out.println(suffixExpression+"的结果是=>"+res);
           // System.out.println(list);
            //中缀表达式对应的集合
            System.out.println("中缀表达式="+expression);
            List<String> strlist = toInfixExpressionList(expression);
            System.out.println("中缀表达式对应的集合"+strlist);
            //后缀表达式对应的集合
            List<String> sufix = parseSuffixExpression(strlist);
            System.out.println(expression+"对应的后缀表达式为:"+sufix);
            //计算中缀表达式转为后缀表达式的结果
            int r = calculate(sufix);
            System.out.println(expression+"的结果为:"+r);
        }
        //接收一个字符串,把字符串分割后放入到集合中
        public static List<String> getList(String suffixExpression){
            String[] splist = suffixExpression.split(" ");
            //String[] splist = suffixExpression.split("#"); // 用#或者空格分割都可以
            List<String> list = new ArrayList<String>();
            //把分割后的每个字符添加到集合中
            for(String item : splist){
                list.add(item);
            }
            return list;
        }
        //把集合中的元素遍历后,进行计算,然后入栈
        /**
         * 思路:
         * 1.从左到右扫描字符串(这里直接遍历集合就可以了),遇到数字就放入到栈中
         * 2.遇到符号后,从栈中pop出两个数,进行计算,然后把计算的结果放到栈中
         * 3.如此反复,最后栈中的数据就是后缀表达式的结果
         * 注意:这里只需要创建一个栈即可,我们只需要把数字放到栈中,遇到符号就直接计算了。
         */
        public static int calculate(List<String> list){
            //创建一个栈
            Stack<String> stack = new Stack<String>();
            //遍历集合
            for (String item : list){
                //这里使用正则表达式来取出数字
                if (item.matches("\\d+")){ //匹配出是否是数字(多位数也能匹配)
                    stack.push(item);
                }else {
                    //不是数字的话,就从栈中pop出两个数,进行计算
                    //定义变量来接收数据
                    int num1 = Integer.parseInt(stack.pop());//接收栈顶的数据
                    int num2 = Integer.parseInt(stack.pop());//接收次栈顶的数据
                    int res = 0;//用来接收结果
                    if (item.equals("+")){
                        res = num1 + num2;
                    }else if (item.equals("-")){
                        res = num2 - num1;
                    }else if (item.equals("*")){
                        res = num1 * num2;
                    }else if (item.equals("/")){
                        res = num2 / num1;
                    }else{
                        throw  new RuntimeException("运算符有问题,无法进行计算");
                    }
                    //计算之后把结果入栈,因为栈是String类型的,这里我们把这个结果拼接一个字符串,就实现了int快速转换成String类型了
                    stack.push(""+res);
                }
            }
            //最后栈中的数据就是表达式的结果,我们把这个结果返回就行
            return Integer.parseInt(stack.pop());
        }
        //中缀表达式转换成后缀表达式的方法
        /**
         * 思路:
         * 1.先把给定的字符串表达式扫描出来放到list集合中,这样方便我们后续的操作
         * 2.判断每个字符是运算符还是数字:
         *    2.1 如果是运算符的话就直接放入到list集合中
         *    2.2 如果是数字的话 我们要判断一下这个数是否是一个多位数,如果是多位数,我们把这个数字拼接上之后再放入到list集合中
         * toInfixExpressionList:方法名说明:中缀表达式对应的list集合
         */
        public static List<String> toInfixExpressionList(String expression){
            //先创建一个list集合
            List<String> list = new ArrayList<String>();
            //定义相关变量
            String str ; //用于多位数的拼接
            int i = 0; //一个指针,用来扫描中缀表达式的字符串
            char c; // 用来接收扫描到的每一个字符
            //这里用一个do...while()循环
            do {
                //如果是非数字,直接添加到list集合中
                if((c = expression.charAt(i) ) < 48 || (c = expression.charAt(i)) > 57){
                    list.add("" + c);
                    i++;//后移
                }else{
                    //str每次拼接都重置成""
                    str = "";
                    //循环拼接多位数,ASCII表中 '0'[48]~'9'[57] 大于等于48~小于等于57是数
                    while(i < expression.length() && (c=expression.charAt(i))>=48 && (c = expression.charAt(i))<=57){
                        str += c;
                        i++;//i后移,往后判断是否还有数字
                    }
                    //拼接完多位数后,把数字放到集合中
                    list.add(str);
                }
            }while(i < expression.length());
            return list;
        }
        //中缀表达式转后缀表达式的方法
        public static List<String> parseSuffixExpression(List<String> strList){
            //先创建栈,用来存放符号和数值
            Stack<String> s1 = new Stack<String>();//用来存放符号
            //Stack<String> s2 = new Stack<String>();//用来存放数字
            //因为s2这个栈只有入栈操作 没有出栈操作,到最后还要逆序打印,这里我们可以用一个list集合代替
            List<String> s2 = new ArrayList<String>();
            //从左到右扫描中缀表达式 (即遍历我们传过来的list集合)
            for (String item : strList){
                //如果是一个数,直接加入到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{
                    /**
                     *  如果s1不为空,扫描到的运算符的优先级小于或等于栈顶运算符的优先级的话,就将s1中的运算符弹出并压入到s2栈中,然后再转到
                     * (4.1)与s1中新的栈顶的运算符进行比较。
                     *  存在的问题:但是我们还缺少一个比较运算符优先级的方法
                     */
                    while(s1.size()!=0 && Operation(item) <= Operation(s1.peek())){
                        s2.add(s1.pop());
                    }
                    //然后把当前扫描到的运算符压入到s1中
                    s1.push(item);
                }
            }
            //将s1中剩余的运算符依次弹出,并压入到s2中
            while(s1.size()!=0){
                s2.add(s1.pop());
            }
            return s2;
    
        }
    
        //比较运算符优先级的方法
        public static  int Operation(String str){
            int result = 0;//用于返回优先级
            switch (str){
                case "+" :
                    result = 1;
                    break;
                case "-" :
                    result = 1;
                    break;
                case "*" :
                    result = 2;
                    break;
                case "/" :
                    result = 2;
                    break;
                default:
                    result = 0; //如果不是这四个运算符 就默认返回0(比如是括号的时候,就返回0,括号在栈外优先级最高,在栈内优先级最低)
                    break;
            }
            return result;
        }
    }
    

    更多相关内容
  • 本文实例为大家分享了C++实现中缀表达式转后缀表达式的具体代码,供大家参考,具体内容如下 题目:现有中缀表达式如:1+(2-3)*4+10/5 请用栈的特性编写一个程序,使得程序输出后缀表达式 分析如下: STEP1: 1+(2-3)...
  • (1) 从键盘或文件读入一个合法的算术表达式,输出相应的后缀表达式后缀表达式中,数据与数据之间加分隔符; (2) 输出正确的计算结果,保留两位小数点; (3) 考虑算法的健壮性,当表达式错误时,要给出错误...
  • 中缀表达式转换为后缀表达式(oj题库) 中缀表达式转换为后缀表达式(oj题库) 题目描述 中缀表达式是一个通用的算术或逻辑公式表示方法,操作符是以中缀形式处于操作数的中间(例:3 + 4),中缀表达式是人们常用的...
  • 本文实例为大家分享了C语言实现中缀表达式转后缀表达式的具体代码,供大家参考,具体内容如下 中缀表达式转换为后缀表达式(思路) 1.创建栈 2.从左向右顺序获取中缀表达式 a.数字直接输出 b.运算符 情况一:遇到左...
  • 本文实例为大家分享了C语言实现对后缀表达式(逆波兰表达式)的求解代码,供大家参考,具体内容如下 逆波兰表达式: 逆波兰表达式又叫后缀表达式。它是由相应的语法树的后序遍历的结果得到的。 例:5 – 8*(6 + 7) +...
  • C++的后缀表达式计算器,运用栈,可以方便地得出浮点数运算的结果。支持的运算符有+、-、*、/、&、|、^、<(左移)、>(右移)、`(乘方)、!(整数阶乘)、\(绝对值),其中整数阶乘和绝对值是单目运算符,其它的...
  • 文章目录前缀表达式(波兰表达式)前缀表达式分析与介绍思路分析中缀表达式中缀表达式分析与介绍后缀表达式(逆波兰表达式)后缀表达式分析与介绍思路分析逆波兰计算器代码实现逆波兰计算器中缀表达式转换为后缀...
  • ////数字与运算符直接要有空格 //#include //#include //#include //#include //using namespace std; //char s[10000]; //stack<int> p; //long long x,y; //int main(){ ...// y=p.t
  • 中缀后缀表达式

    2018-02-23 16:40:12
    包含中缀转后缀以及后缀表达式计算(或中缀记法)是一个通用的算术或逻辑公式表示方法, 操作符是以中缀形式处于操作数的中间(例:3 + 4),中缀表达式是人们常用的算术表示方法。 与前缀表达式(例:+ 3 4)或后缀...
  • 数据结构C++版,将中缀表达式变换为后缀并用后缀表达式求值,支持运算符包括+,-,*,/,^,(),支持小数,负数,多位数运算
  • 选择输入前中后缀表达式,建立表达式二叉树,再前序中序后序遍历二叉树,输出三种形式的表达式
  • std::string src = argc > 1 ? argv[1] : "12+((2+73)*4)-15"; std::cout ; Expression expression; Expression::PrefixType result; int ret = expression.ToPrefix(src, result); if (ret !... }
  • 输入一表达式,将其用表达式树表示,并用表达式数计算表达式的值。
  • 自定义栈,中缀表达式转换为后缀表达式并求值,三个抽象数据类型定义(1.class stack 2.class Middle_expressionToPost_expression 3.class Post_expression_value)
  • 该程序实现了运算表达式转换为中缀表达式、中缀表达式转换为后缀表达式后缀表达式求值。该程序已实现加减乘除括号运算符及求余、幂指数的求解
  • java使用后缀表达式实现计算器,其中有将一般数学运算式(7-9+5/5-5*6)转换成后缀表达式的方法,以及后缀表达式的求解方法
  • 先写词法分析的源文件,用正则表达式表示出需要识别的字符,例如数字,乘法,加法和括号,如果识别到其他非法字符需要报错,用flex生成lex.yy.c文件。语法分析用LR方法进行语法分析,LR方法需要先根据文法构造自动机...
  • 算法设计与分析 实验报告 - PAGE 1 - 实验目的 掌握栈后进先出的特点 掌握栈的典型应用后缀表达式求值 实验内容 用键盘输入一个整数后缀表达式操作数的范围是09运算符只含*/而且中间不可以有空格使用循环程序从左向...
  • 主要为大家详细介绍了C++实现中缀表达式转后缀表达式,文中示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下
  • 本文使用实现了MATLAB实现中缀表达式转后缀表达式并计算(数字包含0-9,符号包含+-*、())后缀表达式得到结果,下面是原理和代码。代码可以在CSDN中下载。
  • 利用栈和队列实现后缀表达式转中缀表达式,win32+vs2013实现
  • 表达式树的形式进行编码,能够输出结点和右节点,以及右节点的右节点(如果存在)的表达式符号,并且输出计算结果。
  • 用dev c++写的代码,附有啰里啰嗦的注释和测试样例。太简单了不好意思要分。
  • 前缀表达式转后缀表达式,及后缀表达式计算器[Java]前缀表达式转后缀表达式 前缀表达式转后缀表达式 总体思路: 创建一个字符型的顺序栈栈和字符型的顺序表存放数字和运算符(顺序表和顺序栈创建参考1,2篇)。 将...

    前缀表达式转后缀表达式,及后缀表达式计算器[Java]

    前缀表达式转后缀表达式

    总体思路:

    1. 创建一个字符型的顺序栈栈和字符型的顺序表存放数字和运算符(顺序表和顺序栈创建参考1,2篇)。
    2. 将表达式符号两边插入空格(分割时就不会10分成1,0)后按空格分割。
    3. 遍历分割后的表达式:若遍历到数字则直接进顺序表;
    4. 若为运算符则先判断,栈若为空或栈顶是左括号或栈顶运算符优先级低于遍历到的运算符,则进栈,否则先栈内运算符出栈至顺序表直到满足进栈条件;若为左括号则直接进栈;若为右括号则栈内运算符一直出栈至顺序表直到栈顶为左括号,同时左括号出栈(不要了);
    5. 最后遍历顺序表,输出后缀表达式。

    以(10+20/2*3)+2+8/4为例,输出结果为10 20 2 / 3 * + 2 + 8 4 / +

    package p2.线性结构;
    //前缀表达式转后缀表达式
    public class InfixToSuffix {
        public static void main(String[] args) {
            String expression = "(10+20/2*3)+2+8/4";
            expression = infixtosuffix(expression);
            System.out.println(expression);
        }
    
        public static String infixtosuffix(String expression){ //开始进行前缀转后缀
            ArrayStack<String> opStack = new ArrayStack<>();
            ArrarList<String> suffixList = new ArrarList<>();
            expression =  insertblank(expression); //空格插入方法
            String[] tokens = expression.split(" ");
            for (String token:tokens){
                if (token.length() == 0){ //若token为空字符串则跳过,遍历下一个
                    continue;
                }else if (isOperator(token)){ //当遍历到运算符,判断是进栈还是弹栈至顺序表
                    while (true){
                        if (opStack.isEmpty() || opStack.peek().equals("(") || priority(opStack.peek()) < priority(token)){
                            opStack.push(token);
                            break;
                        }
                        suffixList.add(opStack.pop());
                    }
                }else if (token.equals("(")){
                    opStack.push(token);
                }else if (token.equals(")")){
                    while (!opStack.peek().equals("(")){ //栈顶不为(的话就一直弹栈
                        suffixList.add(opStack.pop());
                    }
                    opStack.pop();
                }else if (isNumber(token)){
                    suffixList.add(token);
                }else { //若为其他符号则抛出异常
                    throw new IllegalArgumentException("wrong char:" + expression);
                }
            }
            while (!opStack.isEmpty()){
                suffixList.add(opStack.pop());
            }
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < suffixList.size(); i++) {
                sb.append(suffixList.get(i));
                sb.append(' ');
            }
            return  sb.toString();
        }
    
        //判断运算符的优先级
        private static int priority(String token) {
            if (token.equals("+") || token.equals("-")) {
                return 0;
            }
            if (token.equals("*") || token.equals("/")) {
                return 1;
            }
            return -1;
        }
    
        //判断是否为数字
        private static boolean isNumber(String token) {
            return token.matches("\\d+");
        }
    
        //判断是否是运算符
        private static boolean isOperator(String token) {
            return token.equals("+") || token.equals("-") || token.equals("*") || token.equals("/");
        }
    
        //空格插入方法
        private static String insertblank(String expression){
            StringBuilder sb = new StringBuilder();
            for (int i = 0;i< expression.length();i++){
                char c = expression.charAt(i);
                if (c == '('|| c==')'|| c=='+' || c=='-' || c== '*' || c=='/'){
                    sb.append(' ');
                    sb.append(c);
                    sb.append(' ');
                }else {
                    sb.append(c);
                }
            }
            return sb.toString();
        }
    }
    

    后缀表达式计算器

    1. 先将表达式转成后缀表达式(符号间已插入空格)
    2. 创建一个整形的顺序栈
    3. 遍历表达式:如果遍历到数字则直接进栈;如果是运算符则弹栈两个数字进行运算并入栈(后弹栈的运算时放前面)
    4. 最后返回数字栈弹栈的结果
    package p2.线性结构;
    //后缀表达式的计算器
    public class SuffixCalculator {
        public static void main(String[] args) {
            String infixExpression = "(10+20/2*3)/2+8";
            String suffixExpression = InfixToSuffix.infixToSuffix(infixExpression);//调用InfixToSuffix类的infixToSuffix方法
            int result = evaluateSuffix(suffixExpression);
            System.out.println(result);
        }
    
        private static int evaluateSuffix(String expression) {
            ArrayStack<Integer> stack = new ArrayStack<>();
            String[] tokens = expression.split(" ");
            //10 20 2 / 3 * + 2 + 8 4 / +  
            for (String token : tokens) {
                if (token.length() == 0) {//若token为空字符串则跳过,遍历下一个
                    continue;
                }
                if (isNumber(token)) {
                    stack.push(new Integer(token));
                } else {
                    processAnOperator(stack,token);//如果遇到运算符则弹栈两个数字运算,运算后再进栈
                }
            }
            return stack.pop();
        }
    
        private static void processAnOperator(ArrayStack<Integer> stack, String token) {
            int num1 = stack.pop();
            int num2 = stack.pop();
            if (token.equals("+")) {
                stack.push(num2 + num1);
            } else if (token.equals("-")) {
                stack.push(num2 - num1);
            } else if (token.equals("*")) {
                stack.push(num2 * num1);
            } else if (token.equals("/")) {
                stack.push(num2 / num1);
            }
        }
    
        private static boolean isNumber(String token) {
            return token.matches("\\d+");
        }
    }
    
    展开全文
  • 08.中缀表达式转换后缀表达式算法.ppt
  • 【PTA】后缀表达式 (中缀表达式转化为后缀表达式

      

    目录

    1.题目描述

    2.输入输出

    3.解题思路

    4.样例解析 

    5.代码实现

    1.题目描述

    所谓后缀表达式是指这样的一个表达式:式中不再引用括号,运算符号放在两个运算对象之后,所有计算按运算符号出现的顺序,严格地由左而右进行(不用考虑运算符的优先级)。

    如:中缀表达式 3*(5–2)+7 对应的后缀表达式为:352-*7+ 。

    请将给出的中缀表达式转化为后缀表达式并输出。


     2.输入输出


    输入样例: 

    2+4*8+(8*8+1)/3

    输出样例:

    248*+88*1+3/+


     3.解题思路

    对于中缀表达式转换为后缀表达式,我们需要用以下步骤来解决这个问题:

    1. 初始化一个个栈:运算符栈S1
    2. 从左往右开始扫描中缀表达式
      1. 遇到数字,直接输出
      2. 遇到运算符:
        1. 若为 '('  直接入栈
        2. 若为 ')'  将符号栈中的元素依次出栈并输出,直到 '(', '(' 只出栈,不输出
        3. 若为其他符号,将符号栈中的元素依次出栈并将其输出,直到遇到比当前符号优先级更低的符号或者 '('。将当前符号入栈。
        4. 扫描完后,将栈中剩余的符号依次输出。

    4.样例解析 

    下面以 a + b * c +(d * e + f) * g 为例子来讲讲计算机的转换过程。

    1.从左向右开始遍历表达式,首先遇到a, 直接将其输出

        此时输出 :a

        栈的情况:空

    2.继续遍历表达式,遇到+,此时栈空,则将其放入栈中

        此时输出 :a

        栈的情况:+

    3.继续遍历表达式,遇到b,直接将其输出

        此时输出 :a b

        栈的情况:+

    4.继续遍历表达式,遇到*,因为*的优先级大于栈顶的+,所以将*入栈

        此时输出 :a b

        栈的情况:+*

    5.继续遍历表达式,遇到c,直接将其输出

        此时输出 :a b c

        栈的情况:+*

    6.继续遍历表达式,遇到+, 因为+的优先级低于栈顶的*,所以将栈顶的*弹出;然后新的栈顶元素的+与当前的+优先级相同,所以也要将+弹出;然后栈空了,将现在这个+放入栈中

        此时输出 :a b c * + 

        栈的情况:+

    7.继续遍历表达式,遇到(,直接将其放入栈中,不遇到)不会将(弹出。

         此时输出为:a b c * + 

         栈的情况为:+(

    8.继续遍历表达式,遇到d,直接将其输出

         此时输出为:a b c * + d

         栈的情况为:+(

    9.继续遍历表达式,遇到*,因为栈顶为(,不遇到)不将(弹出,故直接将*放入栈中。

           此时输出为:a b c * + d

           栈的情况为:+(*

    10.继续遍历表达式,遇到e,直接将其输出

           此时输出为:a b c * + d e

           栈的情况为:+(*

    11.继续遍历表达式,遇到+,因为+比栈顶*的优先级低,故将*弹出;新的栈顶元素为(,不遇到)不弹出(,故将+放入栈中。

    此时输出为:a b c * + d e *

    栈的情况为:+(+

    12.继续遍历表达式,遇到f,直接将其输出

          此时输出为:a b c * + d e *  f

          栈的情况为:+(+

    13.继续遍历表达式,遇到),直接将栈中元素依次弹出并输出直到遇到(为止,注意:(弹出但不输出

           此时输出为:a b c * + d e *  f + 

           栈的情况为:+

    14.继续遍历表达式,遇到*,因为*的优先级大于栈顶元素+的优先级,故直接将*入栈。

            此时输出为:a b c * + d e *  f + 

            栈的情况为:+ * 

    15.继续遍历表达式,遇到g,直接将其输出。

            此时输出为:a b c * + d e *  f + g

            栈的情况为:+ * 

    16.继续遍历表达式,为空,遍历结束。将栈内元素依次弹出。

            此时输出为:a b c * + d e *  f + g * +

            栈的情况为:空

    至此,中缀表达式转后缀已经全部完成,结果为 a b c * + d e *  f + g * +


    5.代码实现

       5.1.优先级确认

    int priority(char op)
    {
        int priority;
        if(op == '*' || op == '/') priority = 2;
        if(op == '+' || op == '-') priority = 1;
        if(op == '(') priority = 0;
        return priority;
    }
    

         5.2.转换函数

    //引用符号提高转换效率
    void Trans(string &str, string &str1)
    {
        stack<char> s;
        int i;
        for(i = 0; i < str.size(); i ++ )
        {
            //是数字的情况下直接输出
            if(str[i] >= '0' && str[i] <= '9' || str[i] >= 'a' && str[i] <= 'z')
            {
                str1 += str[i];
            }
            else //不是数字的情况分类讨论进行判断
            {
                //栈为空时直接入栈
                if(s.empty()) s.push(str[i]);
                //左括号入栈
                else if(str[i] == '(') s.push(str[i]);
                //如果是右括号,只要栈顶不是左括号,就弹出并输出
                else if(str[i] == ')')
                {
                    while(s.top() != '(')
                    {
                        str1 += s.top();
                        s.pop();
                    }
                    //弹出左括号,但不输出
                    s.pop();
                }
                else 
                {
                    //栈顶元素的优先级大于等于当前的运算符,就将其输出
                    while(priority(str[i]) <= priorty(s.top()))
                    {
                        str1 += s.top();
                        s.pop();
                        //栈为空,停止
                        if(s.empty()) break;
                    }
                    s.push(str[i]);
                }
            }
        }
        //最后,如果不为空,就把所以的元素全部弹出
        while(!s.empty())
        {
            str1 += s.top(); 
            s.pop();
        }
    }

    #include <iostream>
    #include <cstring>
    #include <stack>
    
    using namespace std;
    
    int priority(char op)
    {
        int priority;
        if(op == '*' || op == '/') priority = 2;
        if(op == '+' || op == '-') priority = 1;
        if(op == '(') priority = 0;
        return priority;
    }
    
    //引用符号提高转换效率
    void Trans(string &str, string &str1)
    {
        stack<char> s;
        int i;
        for(i = 0; i < str.size(); i ++ )
        {
            //是数字的情况下直接输出
            if(str[i] >= '0' && str[i] <= '9' || str[i] >= 'a' && str[i] <= 'z')
            {
                str1 += str[i];
            }
            else //不是数字的情况分类讨论进行判断
            {
                //栈为空时直接入栈
                if(s.empty()) s.push(str[i]);
                //左括号入栈
                else if(str[i] == '(') s.push(str[i]);
                //如果是右括号,只要栈顶不是左括号,就弹出并输出
                else if(str[i] == ')')
                {
                    while(s.top() != '(')
                    {
                        str1 += s.top();
                        s.pop();
                    }
                    //弹出左括号,但不输出
                    s.pop();
                }
                else 
                {
                    //栈顶元素的优先级大于等于当前的运算符,就将其输出
                    while(priority(str[i]) <= priorty(s.top()))
                    {
                        str1 += s.top();
                        s.pop();
                        //栈为空,停止
                        if(s.empty()) break;
                    }
                    s.push(str[i]);
                }
            }
        }
        //最后,如果不为空,就把所以的元素全部弹出
        while(!s.empty())
        {
            str1 += s.top(); 
            s.pop();
        }
    }
    
    int main()
    {
        //输入前缀表达式
        string infix;
        string postfix;
        cin >> infix;
        
        Trans(infix, postfix);
        
        cout << postfix << endl;
        return 0;
    }
    展开全文
  • NULL 博文链接:https://128kj.iteye.com/blog/1622059

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 150,255
精华内容 60,102
关键字:

后缀表达式