利用栈将中缀表达式转换成后缀表达式并计算

淩亂°似流年 2022-11-04 12:27 154阅读 0赞

# 一、第一版（未参考别人） #

import java.util.Deque;
    import java.util.HashMap;
    import java.util.LinkedList;
    import java.util.Map;
    
    /**
     * v1 需求：利用栈将中缀表达式转换成后缀表达式并计算
     */
    public class StackTest3 {
        public static void main(String[] args) {
            String i = "1+2*(9-5)";
    //        String i = "1*2+(9-5)";
            System.out.println(calsulate(getSuffixStack(i)));
        }
    
        /**
         * 获取后缀表达式
         * @param input  中缀表达式
         * @return
         */
        public static String getSuffixStack(String input){
            Deque<Character> suffixStack = new LinkedList<>(); //后缀表达式栈
            Deque<Character> operationStack = new LinkedList<>();  //操作符栈
    
            Map<String,Integer> map = new HashMap<>();
            map.put("+",1);
            map.put("-",1);
            map.put("*",2);
            map.put("/",2);
            map.put("(",0);
            map.put(")",0);
    
            char[] chars = input.toCharArray();  //中缀字符串表达式转成数组
            for(int i = 0; i< chars.length; i++){
                if((chars[i] + "").matches("\\d")){  //如果是数字直接放入后缀表达式栈
                    suffixStack.push(chars[i]);
                }else{
                    if(operationStack.isEmpty() || (chars[i]+"").equals("(")){//如果操作符栈为空或者是左括号直接放入操作符栈
                        operationStack.push(chars[i]);
                    }
                    //操作符大的话直接放入操作符栈
                    else if(operationStack.peek() != null && (map.get(operationStack.peek()+"") <= map.get(chars[i]+""))){
                        operationStack.push(chars[i]);
    
                    }else if(")".equals(chars[i]+"")){  //插入右括号
                        while(operationStack.peek() != null && !(operationStack.peek()+"").equals("(")){
                            suffixStack.push(operationStack.pop());
                        }
                        operationStack.pop();//再取出左括号
                    }
                    else{
                        //如果当前操作符比上一个操作符小，则把上一个放入后缀表达式，把当前的放入操作符栈
                        suffixStack.push(operationStack.pop());
                        operationStack.push(chars[i]);
                    }
                }
                continue;
            }
    
            //最后把操作符栈剩下的操作符全部放入后缀表达式
            while(!operationStack.isEmpty()){
                suffixStack.push(operationStack.pop());
            }
    
            StringBuilder s = new StringBuilder();
            while(!suffixStack.isEmpty()){
                s.append(suffixStack.pop());
            }
            return s.reverse().toString();
        }
    
        public static String calsulate(String in ){
            char[] chars = in.toCharArray();
            Deque<String> stack = new LinkedList<>();
            for(int i = 0; i< chars.length; i++){
                if((chars[i]+"").matches("\\d")){
                    stack.push(chars[i]+"");
                    continue;
                }else{
                    String lastNumber = stack.pop();
                    String lastBeforeNumber = stack.pop();
                    Integer result = 0;
                    switch ( chars[i]){
                        case '+': result = Integer.parseInt(lastBeforeNumber) + Integer.parseInt(lastNumber); break;
                        case '-': result = Integer.parseInt(lastBeforeNumber) - Integer.parseInt(lastNumber); break;
                        case '*': result = Integer.parseInt(lastBeforeNumber) * Integer.parseInt(lastNumber); break;
                        case '/': result = Integer.parseInt(lastBeforeNumber) / Integer.parseInt(lastNumber); break;
                        default:
                            System.out.println("运算符不合法");
                    }
                    stack.push(result.toString());
                    continue;
                }
            }
            return stack.pop();
        }
    
    
    }

# 二、第二版（升级版） #

import java.util.*;
    import java.util.regex.Matcher;
    import java.util.regex.Pattern;
    
    /**
     * v2  需求：利用栈将中缀表达式转换成后缀表达式并计算
     */
    public class StackTest4 {
        public static void main(String[] args) {
            String i = "1+2*(9-5)";
    //        String i = "1*2+(9-5)";
            SuffixExpression suffixExpression = getSuffixExpression(i);
            int result = suffixExpression.execute();
    
            if(result == 9){
                System.out.println("测试成功");
            }else{
                System.out.println("测试失败");
            }
        }
    
        public static SuffixExpression getSuffixExpression(String input){
            //后缀表达式栈
            Deque<String> suffixStack = new LinkedList<>();
    
            //操作符栈
            Deque<String> operationStack = new LinkedList<>();
    
            //为运算符设置优先级
            Map<String,Integer> map = new HashMap<>();
            map.put("+",1);
            map.put("-",1);
            map.put("*",2);
            map.put("/",2);
            map.put("(",0);
            map.put(")",0);
    
            //把要匹配的字符串写成正则表达式，这里匹配数字和运算符
            Pattern pattern = Pattern.compile("\\d+|[\\+\\-\\*\\/\\(\\)]");
            Matcher matcher = pattern.matcher(input);
            //若有匹配到就执行该方法体
            while(matcher.find()){
                //获取匹配到的字符
                String current = matcher.group();
                //不是运算符的都直接放入后缀表达式
                if(!map.containsKey(current)){
                    suffixStack.push(current);
                    continue;
                }
    
                //如果运算符是左括号或者操作符栈当下是空，直接将运算符放入操作符栈
                if(current.equals("(") || operationStack.isEmpty()){
                    operationStack.push(current);
                    continue;
                }
    
                //如果遇到右括号，取操作符栈的顶部元素进行判断，同时把元素全部依次放入后缀表达式，直到顶部元素是左括号则退出
                if(current.equals(")")){
                    String top = operationStack.pop();
                    while(!top.equals("(")){
                        suffixStack.push(top);
                        top = operationStack.pop();
                    }
                    continue;
                }
    
                //1、当前操作符的优先级比操作符的顶部元素高，则直接压入操作符栈，后面往出倒的时候，操作符栈里面优先级高的会先出栈，
                // 满足优先级高先运算原则
                //2、当前操作符的优先级比操作符的顶部元素低，则把操作符的顶部元素拿出放入后缀表达式栈，然后把当前元素放入操作符栈
                if(map.get(current) >= map.get(operationStack.peek())){
                    operationStack.push(current);
                }else{
                    suffixStack.push(operationStack.pop());
                    operationStack.push(current);
                }
            }
    
            //最后将操作符栈的所有元素倒入后缀表达式栈
            while(!operationStack.isEmpty()){
                suffixStack.push(operationStack.pop());
            }
    
            return new SuffixExpression(suffixStack);
    
    
        }
    
    }
    
    /**
     * 后缀表达式类
     * 写该类的目的：将中缀表达式需要编译成一个后缀表达式，表达式是一个名词，而且该表达式有可以计算的动作，所以形成了类，
     * 名词即属性，动作即方法
     */
    class SuffixExpression{
        //后缀表达式
        private Deque<? extends String> suffix;
    
        //构造方法
        public SuffixExpression(Deque<? extends String > suffix){
           this.suffix = suffix;
        }
    
        /**
         * 对后缀表达式进行计算
         * @return
         */
        public int execute(){
            //初始化结果栈
            Deque<Integer> resultStack = new LinkedList<>();
    
            //判断后缀表达式是否为空，如果不为空则一直从里面取元素
            while(!suffix.isEmpty()){
                //[+ * - 5 9 2]  依次取出元素
                String value= suffix.pollLast();
                if(value.matches("\\d")){
                    //只要是数字依次放入结果栈
                    resultStack.push(Integer.parseInt(value));
                }else{
                    //如果是非数字则在结果栈取出最新的两个数字
                    int lastNumber = resultStack.pollFirst();
                    int lastBeforeNumber = resultStack.pollFirst();
    
                    //后缀表达式的计算
                    resultStack.push(operate(lastBeforeNumber,lastNumber,value));
                }
            }
            return resultStack.pop();
        }
    
    
        /**
         * 简单计算
         * @param var1  被操作数
         * @param var2  操作数
         * @param operator 运算符
         * @return
         */
        public static int operate(int var1,int var2, String operator){
            int result = 0;
            switch (operator){
                case "+": result = var1 + var2; break;
                case "-": result = var1 - var2; break;
                case "*": result = var1 * var2; break;
                case "/": result = var1 / var2; break;
                default:
                    System.out.println("运算符不合法");
            }
            return  result;
        }
    
    }

# 三、知识点 #

1、分析如何解耦，什么样的情况下需要重新写类，如果该类的形成有属性也有操作方法则可考虑添加新的类

2、Deque的使用，参考：[https://www.liaoxuefeng.com/wiki/1252599548343744/1265121668997888][https_www.liaoxuefeng.com_wiki_1252599548343744_1265121668997888]

3、正则表达式匹配并取出字符：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1N1bl9vZl9SYWlueQ_size_16_color_FFFFFF_t_70][]

4、continue的正确使用

# 四、图解后缀表达式算法逻辑 #

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1N1bl9vZl9SYWlueQ_size_16_color_FFFFFF_t_70 1][]

1，3，5，7数字直接放入操作符栈

2，操作符栈为空的其情况下，符号直接放入操作符栈

3，6 操作符优先级高的情况下直接放入操作运算符栈（第3部画的时候急了，哈哈哈，应该分成两步）

4，左括号直接放入操作符栈

8，遇到右括号，把右括号之前的，左括号后面的运算发全部搬到后缀表达式栈

9，10，最后把操作符栈剩的符号全部搬到后缀表达式栈

# 五、总结比较 #

1、方法名定义需要更精确一些

2、写的方法不应该一股脑放在一个方法体中，应该学会解耦，v2中方法的耦合性就比较低

3、学会使用正则表达是去匹配需要的内容，而不是拆分成数组一个一个比较

4、分析各种情况，以防漏掉某个case

[https_www.liaoxuefeng.com_wiki_1252599548343744_1265121668997888]: https://www.liaoxuefeng.com/wiki/1252599548343744/1265121668997888
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1N1bl9vZl9SYWlueQ_size_16_color_FFFFFF_t_70]: /images/20221023/a7d22dc488584a19915cf7b04af2f639.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1N1bl9vZl9SYWlueQ_size_16_color_FFFFFF_t_70 1]: /images/20221023/9bdb71bd157444bab9b25b4a2b7a7332.png