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

淩亂°似流年 2021-12-20 00:35 432阅读 0赞

分析步骤如下：

1.  初始化两个栈：运算符栈s1和存储中间结果的栈s2
2.  从左至右扫描中缀表达式
3.  遇到操作数时，将其压入s2
4.  遇到运算符时，比较其与s1栈顶运算符的优先级  
    4.1 如果s1为空，或栈顶运算符为左括号“(”，则直接将此运算符入栈；  
    4.2 否则，若优先级比栈顶运算符高，也将运算符压入栈s2  
    4.3 否则，将s1栈顶运算符弹出并加入到s2中，再次转到4.1 与s1中新的栈顶运算符相比较.
5.  遇到括号时：  
    5.1 如果是左括号“(”，则直接压入s1  
    5.2 如果是又括号“)”，则依次弹出s1栈顶的运算符，并压入s2，直到遇到左括号为止，此时将一对左括号丢弃。
6.  重复上述步骤，直到表达式的最右边
7.  将s1中剩余的运算符依次弹出并压入s2
8.  依次弹出s2中的元素并输出，结果的逆序即为中缀表达式对应的后缀表达式

代码实现如下：

/** * @Author: wy * @ProjectName: LFH * @Package: com.feel.algorithm.java * @Description: 将中缀表达式转为后缀表达式 * @Date: Created in 11:26 2019/7/1 */
    public class PolandNotation { 
        public static void main(String[] args) { 
    
            String exp = "1+((2+3)*4)-5";
            List<String> list = toInfixExp(exp);
            System.out.println(list);
    
            List<String> parseList = parseSuffixExp(list);
            System.out.println("后缀表达式" + parseList);
        }
    
        /** * 将得到的中缀表达式对应的list => 后缀表达式对饮的list * * @param list * @return */
        public static List<String> parseSuffixExp(List<String> list) { 
            /*初始化两个栈*/
            Stack<String> s1 = new Stack<String>();
            //Stack<String> s2=new Stack<>();
            List<String> s2 = new ArrayList<>();
    
            for (String item : list) { 
                if (item.matches("\\d+")) { 
                    s2.add(item);
                } else if (item.equals("(")) { 
                    s1.push(item);
                } else if (item.equals(")")) { 
                    while (!s1.peek().equals("(")) { 
                        s2.add(s1.pop());
                    }
                    /*左小括号弹栈*/
                    s1.pop();
                } else { 
                    /*当item的优先级小于等于s1栈顶运算符时，将 * s1栈顶运算符弹出并加入到s2中，再次与s1栈顶元素比较 */
                    while (s1.size() != 0 && Priority.getValue(item) <= Priority.getValue(s1.peek())) { 
                        s2.add(s1.pop());
                    }
                    /*将item压入栈中*/
                    s1.push(item);
                }
            }
            /*将s1中剩余运算符依次加入到s2中*/
            while (s1.size() != 0) { 
                s2.add(s1.pop());
            }
            /*因为是存放到list中，因此按顺序输出就是得到的逆波兰表达式*/
            return s2;
        }
    
    
        /** * 将中缀表达式转为对应的List * * @param s * @return */
        public static List<String> toInfixExp(String s) { 
            List<String> list = new ArrayList<>();
            /*用于遍历中缀字符串的指针*/
            int i = 0;
            /*对多位数进行拼接*/
            String str;
            /*每遍历一个字符，放入到c*/
            char c;
            do { 
                /*如果这是一个非数字，需要加到list中*/
                if ((c = s.charAt(i)) < 48 || (c = s.charAt(i)) > 57) { 
                    list.add("" + c);
                    i++;
                }
                /*如果是一个数字，要考虑多位数*/
                else { 
                    /*先将str置空*/
                    str = "";
                    while (i < s.length() && (c = s.charAt(i)) >= 48 && (c = s.charAt(i)) <= 57) { 
                        str += c;
                        i++;
                    }
                    list.add(str);
                }
            } while (i < s.length());
            return list;
        }
    }
    
    class Priority { 
        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 s) { 
            int result = 0;
            switch (s) { 
                case "+":
                    result = ADD;
                case "-":
                    result = SUB;
                case "*":
                    result = MUL;
                case "/":
                    result = DIV;
                default:
                    //System.out.println("无此操作符");
                    break;
            }
            return result;
        }
    
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，432人围观）

还没有评论，来说两句吧...

相关阅读

相关中缀表达式转换为后缀表达式

一、后缀表达式求值后缀表达式也叫逆波兰表达式，其求值过程可以用到栈来辅助存储。假定待求值的后缀表达式为：6 5 2 3 + 8 \ + 3 + \，则其求值过程如下：

不念不忘少年蓝@/ 2024年02月17日 21:24/ 0 赞/ 45 阅读

相关中缀表达式转后缀表达式

算法遍历中缀表达式中的数字和符号：对于数字直接输出对于符号：左括号：进栈运算

阳光穿透心脏的1/2处/ 2023年10月09日 12:50/ 0 赞/ 52 阅读

相关中缀表达式转换为后缀表达式

[中缀表达式转换为后缀表达式][Link 1] 一、后缀表达式求值后缀表达式也叫逆波兰表达式，其求值过程可以用到栈来辅助存储。假定待求值的后缀表达式为：6 5

一时失言乱红尘/ 2022年08月25日 05:28/ 0 赞/ 217 阅读

相关中缀表达式转换后缀表达式

<pre name="code" class="cpp">include "StdAfx.h" include <stdlib.h> defi

￡神魔★判官ぃ/ 2022年08月08日 05:22/ 0 赞/ 8 阅读

相关计算器：中缀表达式转后缀表达式

这几天想写一个Android的计算器，所以先写好中缀表达式到后缀表达式的计算。例如：中缀表达式(8+9\10)-4/2+3 我们可以进行如下操作： 1、将

绝地灬酷狼/ 2022年08月07日 00:12/ 0 赞/ 268 阅读

相关前缀表达式、中缀表达式、后缀表达式总结

一、前缀表达式（1）定义前缀表达式是一种没有括号的算术表达式，其将运算符写在前面，操作数写在后面。例如表达式1-(2+3)的前缀表达式是- 1 + 2 3。

今天药忘吃喽~/ 2022年07月16日 11:39/ 0 赞/ 413 阅读

相关 java中缀表达式转为后缀表达式

日常生活中，我们使用的数学表达式为中缀表达式例如 6 + 3 \ ( 9 - 7 ) - 8 / 2。后缀表达式的写法将运算符放在数字之后如 6397-\+82/- 可以

谁践踏了优雅/ 2022年06月01日 00:43/ 0 赞/ 249 阅读

相关中缀表达式变为后缀表达式

1.0 什么是中缀表达式很简单 3\（4+2）/2-5 这就是中缀表达式也就是我们常见的算数表达式 2.0 什么是后缀表达式就是把运算符放后面的表达式例如

悠悠/ 2022年05月25日 05:07/ 0 赞/ 317 阅读

相关中缀表达式转换为后缀表达式·

数据结构实验之栈与队列二：一般算术表达式转换成后缀式 Time Limit: 1000 ms Memory Limit: 65536 KiB [Submit][] [S

不念不忘少年蓝@/ 2022年05月18日 02:07/ 0 赞/ 198 阅读

相关中缀表达式转为后缀表达式

分析步骤如下： 1. 初始化两个栈：运算符栈s1和存储中间结果的栈s2 2. 从左至右扫描中缀表达式 3. 遇到操作数时，将其压入s2 4. 遇到运算符时，比较其与s

淩亂°似流年/ 2021年12月20日 00:35/ 0 赞/ 433 阅读