day05-栈实现计算器

栈

使用栈来完成一个表达式的结果

需要的函数：

• 判断是否为运算符
• 判断运算符的优先级
• peek 获得栈顶值
• 运算cal

所需的数据结构：

• 运算表达式
• 数栈 numStack
• 符号栈 operStack
• index来遍历我们的表达式

运算的逻辑：

开始遍历表达式阶段：

1. 如果是一个数字直接入数字栈
2. 如果是运算符，并运算符栈为空就直接入栈。如果占中有运算符就进行比较，如果当前的运算符的优先级小于或者等于栈中的运算符，就要从数栈中pop出两个数并从符号栈中取出一个运算符进行运算，并将结果入数栈。让后将操作符如符号栈。当前的符号栈的优先级大于栈中的符号就直接入栈。

遍历结束收尾阶段：

1. 按照顺序从数栈取出两个数，并从符号栈中取出一个符号进行运算。
2. 到最后数栈中只有一个数字，就是表达式的结果。

ArrayStack2 栈：

package com.summer.stack;

public class ArrayStack2 {

    private int maxSize;
    private int top;
    private int[] stack;

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

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

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

    // 获取栈顶的值
    public int peek(){
        return stack[top];
    }

    // 判断是否是运算符
    public boolean isOperator(int ch){
        return ch == '+' || ch == '-' || ch == '/' || ch == '*';
    }

    //判断运算符的优先级
    public int priority(int ch){
        if ( ch == '+' || ch == '-'){
            return 1;
        } else if (ch == '/' || ch == '*'){
            return 0;
        }else {
            return -1;
        }
    }

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

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

    //出栈 pop
    public int pop(){
        if (isEmpty()){
            throw new RuntimeException("栈为空");
        }
        return stack[top--];
    }

    //遍历数组  从栈顶往栈底遍历数据
    public void show(){
        if (isEmpty()){
            System.out.println("没有数据");
            return;
        }
        for (int i = top; i >= 0; i--) {
            System.out.printf("stack[%d] = %d \n",i,stack[i]);
        }
    }

}

Calculator

package com.summer.stack;

public class Calculator {
    public static void main(String[] args) {
        //[数] expression
        String expression = "3+2*6-10";
        //数栈
        ArrayStack2 numStack = new ArrayStack2(20);
        //操作栈
        ArrayStack2 operStack = new ArrayStack2(20);
        //辅助扫描表达式指针
        int index = 0;
        int num1 = 0;
        int num2 = 0;
        int oper = 0;
        int res = 0;
        char ch = ' ';
        String keepNum = "";
        //开始扫描表达式
        while (true) {//扫描结束条件
            ch = expression.substring(index, index + 1).charAt(0);
            if (operStack.isOperator(ch)) {
                if (!operStack.isEmpty()) {
                    if (operStack.priority(ch) >= operStack.priority(operStack.peek())) {
                        oper = operStack.pop();
                        num1 = numStack.pop();
                        num2 = numStack.pop();
                        res = numStack.calculate(num1, num2, oper);
                        numStack.push(res);
                        operStack.push(ch);
                    } else {
                        operStack.push(ch);
                    }
                } else {
                    operStack.push(ch);
                }
            } else {
                  numStack.push(ch - 48);
            }
            index++;
            if (index >= expression.length()){
                break;
            }
        }

        //扫描结束
        while (true) {
            if (operStack.isEmpty()){
                break;
            }
            oper = operStack.pop();
            num1 = numStack.pop();
            num2 = numStack.pop();
            res = numStack.calculate(num1, num2, oper);
            numStack.push(res);
        }
        System.out.println("结果为：" + numStack.peek());
    }
}

改进：支持多位数的运算

开始处创建一个

 String keepNum = "";

将numStack.push(ch - 48);换成下面的代码

  keepNum += ch;
                if (index == expression.length()-1){
                    numStack.push(Integer.parseInt(keepNum));
                }else {
                    if (operStack.isOperator(expression.substring(index+1,index+2).charAt(0))){
                        numStack.push(Integer.parseInt(keepNum));
                        keepNum = "";
                    }
                }

解释：

将数字加入栈中需要 -48（这里我存入的是char,并不是真正的数字）。因为每个char 其实都是一个数字，比如'0'代表48 ， '1' 就代表49。运算是想让'1'代表1就需要减去48

numStack.push(ch - 48);

image-20200715164521061.png