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

利用栈实现综合计算器(中缀表达式 + 数组实现栈)

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

问题:使用栈完成计算一个表达式的结果,如

思路:使用栈(中缀)完成表达式的计算:

建立两个栈 —— 数栈:存放数据,符号栈:存放运算符。

  1. 通过一个 index(索引)来遍历我们的表达式;
  2. 如果我们发现是一个数字,就直接入栈
  3. 如果扫描到是一个 运算符,需要分情况讨论
    3.1 如果发现当前符号栈为空,则直接入栈;
    3.2 如果符号栈中有符号,则比较两个符号的优先级,如果当前运算符的优先级小于或者等于栈中的操作符,就需要从数栈中 pop 出两个数据、从 符号栈中pop 出一个符号,并进行运算,将运算结果 push 到数栈中,并将当前的运算符入符号栈,如果当前运算符的优先级大于符号栈中栈顶的优先级,则直接将当前的运算符入栈;
  4. 当表达式扫描完成,就依次顺序的从数栈中取出两个数据,从符号栈中取出一个符号,进行运算;
  5. 直到当数栈中只有一个数字,也就是表达式的结果。

第一步:读取到表达式中的index(0)位置,发现为数字,将其放入到数栈中
利用栈实现综合计算器(中缀表达式 + 数组实现栈)
第二步:继续往后读取,发现是运算符,查看符号栈中没有数据,则将其入栈
利用栈实现综合计算器(中缀表达式 + 数组实现栈)
第三步:类比第一步
利用栈实现综合计算器(中缀表达式 + 数组实现栈)
第四步:类比第二步,不过入栈是因为,当前的符号 * 大于符号栈的栈顶元素 +
利用栈实现综合计算器(中缀表达式 + 数组实现栈)
第五步:类比第一步
利用栈实现综合计算器(中缀表达式 + 数组实现栈)
第六步:当前的运算符是 - 而符号栈中栈顶的元素为 * ,- 的优先级小于 * ,则需要从数栈中出两个数据,从符号栈中出一个运算符,并进行运算,然后将运算结果入数栈,并将当前的运算符入符号栈
利用栈实现综合计算器(中缀表达式 + 数组实现栈)
第七步:2 入数据栈,入栈操作完成
利用栈实现综合计算器(中缀表达式 + 数组实现栈)

代码实现:

public class Calculator {
    public static void main(String[] args) {
        String expression = "10+20*4-2";
        // 创建两个栈
        ArrayStack2 numStack = new ArrayStack2(10);  // 数栈
        ArrayStack2 operStack = new ArrayStack2(10);  // 符号栈
        int index = 0; // 用于扫描
        int num1 = 0;
        int num2 = 0;
        int oper = 0;
        int res = 0;
        char ch = ' '; // 将扫描表达式扫描到的值保存到 ch 中
        String num = "";  // 用来拼接多位数的各个位用的
        // 开始扫描 expression 表达式
        while(true){
            // 依次得到 expression 的每一个字符
            ch = expression.charAt(index);
            // 判断 ch 是什么,然后做相应的处理
            if(!Character.isDigit(ch)){ // 判断得到 ch 是运算符
                // 判断符号栈是否为空
                if(!operStack.isEmpty()){ // 判断得到符号栈不为空
                    // 判断当前运算符的优先级 与 符号栈中栈顶运算符优先级的大小关系
                    if(operStack.priority(ch) <= operStack.priority(operStack.peek())){  // 判断得到当前运算符的优先级 小于等于 符号栈中栈顶运算符的优先级
                        // 1. 从数栈中栈顶取出两个数据
                        num1 = numStack.pop();
                        num2 = numStack.pop();
                        // 2. 从符号栈栈顶取出一个数据
                        oper = operStack.pop();
                        // 3. 运算得到结果
                        res = numStack.cal(num1, num2, oper);
                        // 4. 将运算结果入数栈
                        numStack.push(res);
                        // 5. 将当前运算符入符号栈
                        operStack.push(ch);
                    }else{  // 判断得到当前运算符的优先级 大于等于 符号栈中栈顶运算符的优先级
                        // 直接入栈
                        operStack.push(ch);
                    }
                }else{  // 判断得到 符号栈为空
                    operStack.push(ch);
                }
            }else{ // 判断得到 ch 是数字
                // 判断 当前数据是否为多位数
                // 即当前扫描的值是数字,但是下一位还是数字
                // 如果是多位数,不能立即入栈。
                num += ch;

                //  1. 如果 ch 已经是 expression 的最后一位,就不用再判断了,直接入栈即可
                if(index == expression.length() - 1){
                    numStack.push(Integer.parseInt(num));
                }else {
                    // 2. 不是 expression 的最后一位
                    if (!Character.isDigit(expression.charAt(index + 1))) {  // 下一位不是数字
                        numStack.push(Integer.parseInt(num));
                        // 注意:如果下一位不再是数字,一定要将拼接数字用的 num 清空
                        num = "";
                    }
                }
            }
            // 每次扫描,index 往后挪一位
            index++;
            // 入栈结束
            if(index >= expression.length()){
                break;
            }
        }
        // 入栈结束,按序(数栈出两,符号栈出一)计算栈中剩下的值
        while(true){
            // 如果符号栈为空,则计算完毕,此时数栈中只剩下一个数值(即为 表达式结果)
            if(operStack.isEmpty()){
                break;
            }
            num1 = numStack.pop();
            num2 = numStack.pop();
            oper = operStack.pop();
            res = numStack.cal(num1, num2, oper);
            numStack.push(res);
        }
        System.out.printf("表达式 %s = %d",expression,res);
    }
}

// 我们这里用到的栈是自己用数组实现的栈,也可以自己用 Java 的栈,这样就不用写 push、pop等方法了
class ArrayStack2{
    private int maxSize;
    private int[] stack;
    private int top = -1;

    // 构造器

    public ArrayStack2(int maxSize) {
        this.maxSize = maxSize;
        stack = new int[maxSize];
    }

    //判断栈满
    public boolean isFull(){
        return top == maxSize - 1;
    }

    // 判断栈空
    public boolean isEmpty(){
        return top == -1;
    }

    // 入栈
    public void push(int value){
        if(isFull()){
            System.out.println("栈已满");
            return;
        }
        top++;
        stack[top] = value;
    }

    // 出栈
    public int pop(){
        if(isEmpty()){
            // 抛出异常
            throw new RuntimeException("栈空,没有异常");
        }
        return stack[top--];
    }

    // 遍历栈
    public void list(){
        if(isEmpty()){
            System.out.println("栈空");
            return;
        }
        for(int i = top; i >= 0; i--){
            System.out.printf("此时出栈的是 %d",stack[top]);
        }
    }

    // 查看栈顶元素,不取出
    public int peek(){
        if(isEmpty()){
            throw new RuntimeException("栈为空");
        }
        return stack[top];
    }

    // 自定义运算符的优先级目前我们的表达式只能计算 + - * /,若要计算(),只需要在此处 加上 是否为括号的判断
    public int priority(int oper){
        if(oper == '*' || oper == '/'){
            return 1;
        }else if(oper == '+' || oper == '-'){
            return 0;
        }else{
            return -1;
        }
    }

    // 运算
    public int cal(int num1, int num2, int oper){
        int res = 0;
        switch (oper){
            case '+':
                res = num1 + num2;
                break;
            case '-':
                res = num2 - num1;
                break;
            case '*':
                res = num1 * num2;
                break;
            case '/':
                res = num2 / num1;
                break;
            default:
                break;
        }
        return res;
    }
}


运算结果:

利用栈实现综合计算器(中缀表达式 + 数组实现栈)

逆波兰计算器(用后缀表达式实现的计算器)

相关标签: java