回顾数据结构（Java版）——中缀表达式实现简单计算器

蔚落 2023-06-06 07:49 1阅读 0赞

自定义栈并且使用中缀表达式实现计算器，代码中有几个比较容易出错的点，比如多位数的情况，longNumber的清空等等

package com.wrial.calculator;
    /*
     * @Author  Wrial
     * @Date Created in 11:53 2019/10/10
     * @Description 使用栈实现单值计算器（中缀表达式）
     */
    
    
    public class Calculator {
    
        public static void main(String[] args) {
            String aimStr = "10+6/2+5*2";
            int index = 0;//记录分解字符串当前位置
            char anChar; //记录aimStr分解后的单个字符
            int num1;//进行计算的数字1
            int num2;//进行计算的数字2
            int result;//计算的结果
            char operator;//进行计算的操作符
            String longNumber = "";
    
    
            Calculator calculator = new Calculator();
            //1.创建两个栈（数字栈和操作符栈）
            ArrayStack numberStack = new ArrayStack<Integer>();
            ArrayStack operatorStack = new ArrayStack<Character>();
            //2.分解字符串并对应入栈
            for (index = 0; index < aimStr.length(); index++) {
                anChar = aimStr.substring(index, index + 1).charAt(0);
                //3.如果是一个操作符就判断优先级而看是否要进行入栈
                if (calculator.isOperator(anChar)) {
                    //4.如果操作栈是空的，那就直接入栈
                    if (operatorStack.isEmpty()) {
                        operatorStack.push(anChar);
                        //5.如果操作栈不为空，就和前面的操作符号比较优先级（如果当前操作符优先级小于栈顶操作符就出栈计算）
                    } else if (calculator.operatorPrivilege((char) operatorStack.peek())
                            >= calculator.operatorPrivilege(anChar)) {
                        //6.从数字栈中出两个，从符号栈中出一个
                        num1 = (int) numberStack.pop();
                        num2 = (int) numberStack.pop();
                        operator = (char) operatorStack.pop();
                        result = calculator.calculate(num1, num2, operator);
                        System.out.println(num1 + operator + num2 + " = " + result);
                        //7.计算完后将结果放入数字栈
                        numberStack.push(result);
                        //8.将当前操作符放入操作符栈
                        operatorStack.push(anChar);
                        //9.如果优先级大于栈顶就入栈
                    } else {
                        operatorStack.push(anChar);
                    }
                } else {
                    longNumber += anChar;
                    //10.如果index到最后了，就把它入数栈，如果对它进行判断下一个是不是操作符就会出现越界异常
                    if (index == aimStr.length() - 1) {
                        numberStack.push(Integer.parseInt(longNumber));
                        //入栈后必须清空
                        longNumber = "";
                        //11.如果下一个是操作符就得将这个数字串入栈
                    } else if (calculator.isOperator(aimStr.substring(index + 1, index + 2).charAt(0))) {
                        numberStack.push(Integer.parseInt(longNumber));
                        //在入栈后必须要清空
                        longNumber = "";
                    }
                }
            }
            //12.到此，数据扫描阶段就过去了，开始正式的计算阶段,直至运算符栈空
            while (true) {
    
                if (operatorStack.isEmpty()) {
                    System.out.println("计算结束，结果=" + numberStack.peek());
                    break;
                } else {
                    num1 = (int) numberStack.pop();
                    num2 = (int) numberStack.pop();
                    operator = (char) operatorStack.pop();
                    result = calculator.calculate(num1, num2, operator);
                    System.out.println(num1 + operator + num2 + " = " + result);
                    //计算完后将结果放入数字栈
                    numberStack.push(result);
                }
            }
    
    
        }
    
        /*
           如果是加减乘除就返回true
           */
        public boolean isOperator(char operator) {
            switch (operator) {
                case '*':
                case '-':
                case '/':
                case '+':
                    return true;
            }
            return false;
        }
    
        /*
        这里注意的一点就是先入栈的数是后出栈的，因此要将前后反过来
         */
        public int calculate(int num1, int num2, char operator) {
            switch (operator) {
                case '*':
                    return num2 * num1;
                case '-':
                    return num2 - num1;
                case '/':
                    return num2 / num1;
                case '+':
                    return num2 + num1;
            }
            System.err.println("不存在此操作");
            return -1;
        }
    
        /*
        因为操作符入栈的时候要判断等级，如果优先级大于或者等于就入栈，否则就出栈
         */
        public int operatorPrivilege(char operator) {
            if (operator == '*' || operator == '/') {
                return 2;
            }
            if (operator == '+' || operator == '-') {
                return 1;
            }
            System.err.println("暂不支持此操作符");
            return -1;
        }
    
    }
    
    interface Stack<T> {
        /**
         * 栈是否为空
         */
        boolean isEmpty();
    
        /**
         * data元素入栈
         */
        void push(T data);
    
        /**
         * 返回栈顶元素,未出栈
         */
        T peek();
    
        /**
         * 出栈,返回栈顶元素,同时从栈中移除该元素
         */
        T pop();
    
        /**
         * 是否栈满
         */
        boolean isFull();
    
        /**
         * 遍历栈
         */
        void showAll();
    }
    
    class ArrayStack<T> implements Stack {
        private T[] array;
        private int capacity;
        private int top = -1;  //栈顶初始化为-1
    
        ArrayStack(int capacity) {
            this.capacity = capacity;
            array = (T[]) new Object[capacity];
        }
    
        ArrayStack() {
            this.capacity = 16;
            array = (T[]) new Object[16];
        }
    
    
        @Override
        public boolean isEmpty() {
            return top == -1;
        }
    
        @Override
        public void push(Object data) {
            if (isFull()) {
                System.out.println("栈满");
                return;
            }
            top++;
            array[top] = (T) data;
            System.out.println("入栈成功" + array[top]);
    
        }
    
        @Override
        public Object peek() {
            return array[top];
        }
    
        public T pop() {
            if (isEmpty()) {
                System.out.println("栈空");
                return null;
            } else {
                T value = array[top];
                top--;
                System.out.println("出栈成功" + value);
                return value;
            }
        }
    
        @Override
        public boolean isFull() {
            return top == capacity;
        }
    
        //记得遍历栈的时候是从上往下遍历
        @Override
        public void showAll() {
            for (int i = top; i >= 0; i--) {
                System.out.printf("%d\t", array[i]);
            }
        }
    
    }