欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

栈实现综合计算器(中缀表达式)

程序员文章站 2022-05-26 12:01:26
...

栈: 计算器–运算


思路:

  1. 自己定义符号优先级 priority
  2. 判断是否为符号 isOper
  3. 进行运算 cal
  4. 需要两个栈 — 数栈、符号栈
  5. 定义需要的相关变量 index、num1、num2、res、oper、ch
  6. 分解表达式
  7. 判断当前字符 是 数字 还是 符号
    7.1 如果是数字,直接压入数栈中
    7.2 如果是符号
    7.2.1 判断符号栈是否为空
    7.2.2 为空: 将符号直接压入
    7.2.3 不为空: 判断当前符号 与 符号栈栈顶符号的优先级谁高
    7.2.4 当前符号优先级 小于等于 栈顶符号优先级: 将数栈中的pop出两个数,符号栈中pop一个进行运算,运算完后将 res 放入数栈, 然后再将当前符号压入符号栈中。
    7.2.5 当前符号优先级 大于 栈顶符号优先级: 直接压入符号栈
    7.3 判断是否分解到表达式末尾
    7.4 表达式分解完后,对两个栈中剩下的数据进行运算: 数栈pop两个,符号栈pop一个。
    7.5 运算完成的标志: 符号栈为空
    7.6 最后数栈剩下的就是总运算结果

栈实现综合计算器(中缀表达式)




    /**
     * 数组模拟栈
     */
    class ArrayStack<T> {
    // 部分方法
    	/**
         *  返回栈顶数据, 不弹出
         */
        public T peek(){
            return arr[top];
        }

        /**
         * 定义优先级,符号优先级是我们自己来定义的
         * 以数字来表示优先级高低
         */
        public int prioprity(char oper) {
            if (oper == '*' || oper == '/') {
                return 1;
            } else if (oper == '+' || oper == '-') {
                return 0;
            } else {
                return -1;   // 目前只支持 + - * /
            }
        }

        /**
         * 判断是否为符号
         */
        public boolean isOper(char oper) {
            return oper == '*' || oper == '/' || oper == '+' || oper == '-';
        }

        /**
         * 数运算
         */
        public int cal(int num1, int num2, char oper) {
            int res = 0;
            // 实际需要考虑 / 0
            switch (oper) {
                case '*': res = num1 * num2;
                    break;
                case '/': res = num2 / num1;
                    break;
                case '+': res = num1 + num2;
                    break;
                case '-': res = num2 - num1;
                    break;
                default:
            }
            return res;
        }
    }


    @Test
    public void testOperStack(){
        String exp = "3+6*2-2";
        // 需要两个栈
        // 数栈
        ArrayStack numStack = new ArrayStack(10);
        // 符号栈
        ArrayStack operStack = new ArrayStack(10);

        // 定义需要的相关变量
        int index = 0; // 用于扫描
        int res = 0;
        char oper = 0;
        int num1 = 0;
        int num2 = 0;
        char ch = ' '; // 用来接收表达式的字符

        while (true){
            ch = exp.charAt(index++);

            // 判断是否为符号
            if(operStack.isOper(ch)){
                // 判断符号栈是否为空
                if(operStack.isEmpty()){
                    operStack.push(ch);
                }else{
                    // 不为空
                    // 判断当前符号与栈顶符号的优先级
                    if(operStack.prioprity(ch) <= operStack.prioprity((Character) operStack.peek())){
                        num1 = (int) numStack.pop();
                        num2 = (int) numStack.pop();
                        oper = (char) operStack.pop();
                        res = operStack.cal(num1, num2, oper);
                        numStack.push(res);
                        operStack.push(ch);
                    }else {
                        // 如果优先级大于, 直接压入栈中
                        operStack.push(ch);
                    }
                }
            }else{
                // 不是符号
                // 数字直接压入栈中
                numStack.push(ch - 48);
            }
            if(index >= exp.length()){
                break ;
            }
        }

        while (!operStack.isEmpty()){
            num1 = (int) numStack.pop();
            num2 = (int) numStack.pop();
            oper = (char) operStack.pop();
            res = operStack.cal(num1, num2, oper);
            numStack.push(res);
        }
        System.out.println(numStack.pop());

    }



上面存在问题: 连续使用两个减: 3-6*2-2 期望:-11 实际: -7

原因: 表达式分解完后,对剩余数据运算时, 顺序必须从符号栈底向上运算


最后处理数栈、符号栈剩余数据时修改了下:


        ArrayStack t1 = new ArrayStack(10);
        ArrayStack t2 = new ArrayStack(10);
        while(!numStack.isEmpty()){
            t1.push(numStack.pop());  // 相当于从原来的栈底开始运算
        }
        while (!operStack.isEmpty()){
            t2.push(operStack.pop());  // 从栈底开始运算
        }
        while (!t2.isEmpty()){
            num1 = (int) t1.pop();   // 取两个数
            num2 = (int) t1.pop();
            oper = (char) t2.pop();   // 取一个符号
            res = operStack.cal(num2, num1, oper);
            t1.push(res);
        }

        System.out.println(t1.pop());




多位数问题: 根据上面的计算一位数的代码

只要修改 判断分解出来的是 数字 还是 符号 的 数字那块逻辑
思路:

  1. 定义 String keepNum = “”; // 用于拼接多位数的.
  2. 进行数字拼接
  3. 继续判断下一位是否为数字
    3.1 是数字: 继续拼接,判断下一位…
    3.2 不是数字: 结束循环, 注意下标问题 !
  4. 最后将 keepNum 重置 !

			else{
                // 不是符号,但是不能直接进入数栈
                keepNum += ch;
                while (index < exp.length()){
                    ch = exp.charAt(index++);  // 有安全隐患
                    if(!numStack.isOper(ch)){
                        keepNum += ch;
                    }else {
                        // 此时判断出符号了,再减1回到这个符号交给上面取判断
                        index--;
                        break ;
                    }
                    // 防止越界
                }
                // 压入数栈
                numStack.push(Integer.parseInt(keepNum));

                // 记得重置 keepNum
                keepNum = "";
            }