【java数据结构与算法学习】中缀表达式转后缀表达式

清疚 2022-05-30 05:08 138阅读 0赞

通常我们的计算方式都是中缀表达式，如何转化为后缀表达式呢？

主要的思想就是：我们创建一个操作符栈，当我们遇到数字的时候就直接进行保存或者输出；当我们遇到操作符 s 的时候，就看一下栈顶元素的优先级是否大于等于当前操作符 s ，如果大于等于，我们就进行出栈操作，然后将当前操作符 s 入栈；如果小于当前操作符 s ，我们就仅将当前操作符 s 入栈；最后将栈中的所有操作符全部弹出。

先乘除后加减，同级别的先来后到

import java.util.Arrays;
    import java.util.Scanner;
    
    public class ZhongZhuiZhuanHouZhui {
        //中缀表达式转后缀表达式，需要用到一个栈
        //首先我们来创建一个栈
        private Object[] objects;
        private int theSize;
        private int top;
    
        public ZhongZhuiZhuanHouZhui(){
            theSize = 20;
            top = -1;
            objects = new Object[theSize];
        }
    
        public boolean push(Object o){
            if (top == theSize-1){
                objects = Arrays.copyOf(objects, theSize + theSize/2);
                theSize = theSize+theSize/2;
            }
            objects[++top] = o;
            return true;
        }
        public Object pop(){
            return objects[top--];
        }
        //返回栈顶元素
        public Object peek(){
            if (top < 0){
                return null;
            }
            return objects[top];
        }
        public static void main(String[] args) {
            //创建栈
            ZhongZhuiZhuanHouZhui convert = new ZhongZhuiZhuanHouZhui();
            //接收用户输入，用户输入格式是空格分隔
            Scanner sc = new Scanner(System.in);
            String str = sc.nextLine();
            String[] chs = str.split(" ");
            //用来转换后的后缀表达式
            String[] houZhui = new String[chs.length];
            int i = 0;
            //遍历用户输入
            for (String s :
                    chs) {
                //当遇到“+”的时候，循环判断栈中的操作符是否小于“+”的优先级，如果不小于（大于等于），就出栈，“+”入栈；如果小于，“+”入栈
                if (s.equals("+")){
                    while ("+".equals(convert.peek()) || "-".equals(convert.peek())||"*".equals(convert.peek()) || "/".equals(convert.peek())){
                        houZhui[i++] = (String) convert.pop();
                    }
                    convert.push("+");
                    //当遇到“-”的时候，循环判断栈中的操作符是否小于“-”的优先级，如果不小于（大于等于），就出栈，“-”入栈；如果小于，“-”入栈
                }else if (s.equals("-")){
                    while ("+".equals(convert.peek()) || "-".equals(convert.peek())||"*".equals(convert.peek()) || "/".equals(convert.peek())){
                        houZhui[i++] = (String) convert.pop();
                    }
                    convert.push("-");
                    //当遇到“*”的时候，循环判断栈中的操作符是否小于“*”的优先级，如果不小于（大于等于），就出栈，“*”入栈；如果小于，“*”入栈
                }else if (s.equals("*")){
                    while ("*".equals(convert.peek()) || "/".equals(convert.peek())){
                        houZhui[i++] = (String) convert.pop();
                    }
                    convert.push("*");
                    //当遇到“/”的时候，循环判断栈中的操作符是否小于“/”的优先级，如果不小于（大于等于），就出栈，“/”入栈；如果小于，“/”入栈
                }else if (s.equals("/")){
                    while ("*".equals(convert.peek()) || "/".equals(convert.peek())){
                        houZhui[i++] = (String) convert.pop();
                    }
                    convert.push("/");
                    //当遇到“(”的时候，直接压栈
                }else if (s.equals("(")){
                    convert.push("(");
                    //当遇到“)”的时候，出栈，直到遇到“(”，舍弃“(”
                }else if (s.equals(")")){
                    while (!"(".equals(convert.peek())){
                        houZhui[i++] = (String) convert.pop();
                    }//弹出“(”
                    convert.pop();
                } else {
                    //如果遇到的是数字，那么直接保存
                    houZhui[i++] = s;
                }
            }
            //循环完成，将栈中的操作符弹出
            while (convert.peek() != null){
                houZhui[i++] = (String) convert.pop();
            }
            for (String s:
                houZhui) {
                if (s != null){
                    System.out.print(s+" "); // 3 + ( 2 - 5 ) * 6 / 3
                }
            }
    
        }
    }