Java用栈实现表达式求值

逃离我推掉我的手 2024-04-08 08:49 60阅读 0赞

## 表达式求值 ##

### 实现思路 ###

*  准备一个索引index来帮助我们遍历表达式
 *  如果index位置上的元素是一个数字，就直接入栈
 *  如果index位置上的元素是一个符号
    
     *  如果符号栈为空，直接入栈
     *  如果符号栈不为空
        
         *  index位置上的符号的优先级小于或等于栈顶符号的优先级，则弹出两个数栈中的元素和符号栈中的一个符号，并且进行计算。将运算结果放入数栈中，并将index位置上的符号压入符号栈
         *  index位置上的符号的优先级大于符号栈栈顶符号的优先级，则将该符号压入符号栈
 *  当表达式遍历完毕后，就弹出数栈中的2个数字和符号栈中的1个符号进行运算，并将运行结果入栈
 *  最终数栈中只有一个值，这个值便是运算结果
 *  注意：
    
     *  读取的是字符，所以存入数字前需要减去0的ASCII码
     *  如果数字是多位数，需要一直读，读到下一位不是数字为止，然后将读到的字符进行拼接，然后一起压入数栈

--------------------

### 思路流程图 ###

#### 1、假设表达式是express ####

数字入栈发现入栈的是12字符串，因为12是一个数字，我们不能把他分开所以就必须将连续的数字拼接一起。  
![在这里插入图片描述][336a47f0fb144c9fb0f3235c04179e64.png]

#### 2、拼接数字字符串，比对符号栈优先级 ####

当减号之前和会进行一个比对，当入栈的符号栈小于栈顶的优先级时，符号栈栈顶的运算符会和数字栈顶的两个元素进行运算，将运算结果放入数字栈顶。  
![在这里插入图片描述][4010619f47bc4b229d58b0b7f44023d3.png]

#### 3、计算栈顶元素的优先级 ####

大家学过数学的都知道\*（乘法的优先级大于加法）所以应该先算3\*3

![在这里插入图片描述][e7021d48761a459c9d57732318d5a841.png]

计算得到：  
![在这里插入图片描述][185b6603bd3140b3853d5890d0d51c7a.png]

#### 4、最终得到 ####

![在这里插入图片描述][d5f92cdc5b4b4b8ea1ea74dfc7a33f7d.png]

#### 5、计算最终结果 ####

![在这里插入图片描述][4c99156c1e7747aeb3162343e017f001.png]

--------------------

### 实现代码 ###

package com.cloud;
    
    import java.util.EmptyStackException;
    
    public class Demo2 {
        
        public static void main(String[] args) {
        
            String exps = "12+8*9-9/3";
            //索引，用来读取字符串中的元素
            int index = 0;
            //保存读取到的数字和符号
            int number1 = 0;
            int number2 = 0;
            int thiChar = ' ';
            // 拼接字符串
            StringBuilder sb = new StringBuilder();
            // 数字栈
            ArrayStack numberStack = new ArrayStack(10);
            // 符号栈
            ArrayStack operationStack = new ArrayStack(10);
            // 保存计算结果
            int result;
    
            for (index = 0; index < exps.length(); index++) {
        
                thiChar = exps.charAt(index);
                // 判断字符是不是运算符
                if (operationStack.isOperation(thiChar)){
        
                    // Todo 比较运算符之间的优先级
                    if (operationStack.comparePriority(thiChar)){
        
                        // 入栈的运算符大于栈顶的，直接入栈
                        operationStack.push(thiChar);
                    }else{
        
                        // 入栈的运算符小于栈顶的，将数字栈顶的两个元素进行入栈运算符计算
                        // 栈顶运算符
                        int popChar = operationStack.pop();
                        // 取出数字栈顶的两个元素
                        number2 = numberStack.pop();
                        number1 = numberStack.pop();
                        // 计算结果
                        result = operationStack.calculation(number1, number2, popChar);
                        // 将入栈的运算符入符号栈
                        operationStack.push(thiChar);
                        // 将计算的结果放入数字栈顶
                        numberStack.push(result);
                    }
                    // 数字直接添加到数字栈中
                }else{
        
                    while (thiChar >= '0' && thiChar <= '9'){
        
                        // 数字有可能会是多为，12
                        sb.append(thiChar - '0');
                        System.out.println("拼接字符串"+sb);
                        index++;
                        // 到了最后一位结束
                        if (index >= exps.length()){
        
                            break;
                        }
                        thiChar = exps.charAt(index);
                    }
                    int num = Integer.parseInt(sb.toString());
                    numberStack.push(num);
                    // 初始化sb
                    sb = new StringBuilder();
                    index--;
                }
            }
            // 运算
            while (!operationStack.isEmpty()){
        
                int popChar = operationStack.pop();
                number2 = numberStack.pop();
                number1 = numberStack.pop();
                result = operationStack.calculation(number1,number2,popChar);
                numberStack.push(result);
            }
            System.out.println(numberStack.pop());
    
        }
    }
    
    
    class ArrayStack {
        
        // 栈大小
        private final int maxSize;
        // 栈数组
        int[] stack;
        // 栈顶指针，默认为-1，添加元素top++
        private int top;
    
        /**
         * 初始化栈
         */
        public ArrayStack(int maxSize) {
        
            this.maxSize = maxSize;
            stack = new int[this.maxSize];
            top = -1;
        }
    
        /**
         * 判断是否为空,top=-1,说明栈中没有元素
         *
         * @return top == -1
         */
        public boolean isEmpty() {
        
            return top == -1;
        }
    
        /**
         * 判断栈是否满了，
         *
         * @return
         */
        public boolean isFull() {
        
            return top == maxSize - 1;
        }
    
        /**
         * 添加元素
         *
         * @param i
         */
        public void push(int i) {
        
            if (isFull()) {
        
                System.out.println("栈满了，请不要再进来了");
                return;
            }
            top++;
            stack[top] = i;
        }
    
        /**
         * 从栈顶取出一个元素
         *
         * @return
         */
        public int pop() {
        
            if (isEmpty()) {
        
                System.out.println("栈是空的，请不要在进来取了");
                throw new EmptyStackException();
            }
            int retNum = stack[top];
            top--;
            return retNum;
        }
    
        /**
         * 遍历栈
         */
        public void traverse() {
        
            for (int thiChar : stack) {
        
                System.out.println(thiChar);
            }
        }
    
        /**
         * 判断符号优先级
         *
         * @param operation
         * @return
         */
        public int getPriority(int operation) {
        
            if (operation == '*' || operation == '/') {
        
                return 2;
            } else if (operation == '+' || operation == '-') {
        
                return 1;
            } else if (operation >= '0' && operation <= '9') {
        
                return 0;
            } else {
        
                return -1;
            }
        }
    
        /**
         * 比较符号栈和入栈符号元素的优先级
         *
         * @param operation
         * @return
         */
        public boolean comparePriority(int operation) {
        
            if (isEmpty()) {
        
                return true;
            } else {
        
                int priority1 = getPriority(operation);
                int priority2 = getPriority(stack[top]);
                return priority1 > priority2;
            }
        }
    
        /**
         * 判断输入的是否是一个运算符号
         *
         * @param operation
         * @return
         */
        public boolean isOperation(int operation) {
        
            return operation == '*' || operation == '/' || operation == '-' || operation == '+';
        }
    
        /**
         * 计算
         *
         * @param number1
         * @param number2
         * @param operation
         * @return
         */
        public int calculation(int number1, int number2, int operation) {
        
            switch (operation) {
        
                case '+':
                    return number1 + number2;
                case '-':
                    return number1 - number2;
                case '*':
                    return number1 * number2;
                case '/':
                    return number1 / number2;
                default:
                    System.out.println(operation);
                    throw new RuntimeException("符号读取错误！");
            }
        }
    
    }

--------------------

[336a47f0fb144c9fb0f3235c04179e64.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/57bda9332acf4e2bb7991f5d9a407aef.png
[4010619f47bc4b229d58b0b7f44023d3.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/e97364c3ea314e929a41fe706f3a64cf.png
[e7021d48761a459c9d57732318d5a841.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/d1de42bbb46649ffb045d537475a5b26.png
[185b6603bd3140b3853d5890d0d51c7a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/6e5da05b55e346819088cbe75ea9e765.png
[d5f92cdc5b4b4b8ea1ea74dfc7a33f7d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/ebbc81dbecb14ee1a3871447513c33fb.png
[4c99156c1e7747aeb3162343e017f001.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/ffeeca95762d4dc19d069226257f5d2d.png