用栈实现中缀表达式计算器吧！

啥是栈？

栈概念图

栈是一个暂时存储数据的地方，它有pop(弹栈、出栈)的操作，也有push(入栈)的操作，这一点有点类似于弹匣

弹栈就是取出顶部的一个数据，像这样

而入栈就是反过来的操作。

好了，我们已经知道栈是怎么存储和释放数据了，接下来就让我们来手搓一个栈吧！

用数组制作一个栈吧！

首先，捏出来一个栈类，把构造方法给它整上去(用于初始化对象)

import java.util.Arrays;

public class StackObject {
    double[] arrayStack;//存储双精度浮点数的“栈”(以后用于小数运算)
    int stackSize;
    int index = -1;//备注：index是“指针”的位置，-1代表栈底，0代表从下往上数第一个元素，以此类推
    public StackObject(int stackSize){
        this.stackSize = stackSize;
        arrayStack = new double[stackSize];
    }
}

接下来，我们实现弹栈(pop)和入栈(push)的操作，在此之前，我们可以写两个工具方法：判断栈满核栈空的方法

public boolean isEmpty(){
    return index == -1;
}
public boolean isFull(){
    return index == (stackSize - 1);
}

pop和push

public void push(double data){//为栈添加元素
    if(isFull()){
        throw new RuntimeException("错误：栈已满");
    }else {
        index++;//指针上移
        arrayStack[index] = data;//修改指针上移后栈帧的数值
    }
}

public double pop(){//从栈取出元素
    if(isEmpty()){
        throw new RuntimeException("错误：栈已空");
    }else {
        double data = arrayStack[index];
        index--;//弹出了一个数据，指针往下移动(将弹出的数据忽略，相当于删除)
        return data;
    }
}

除此之外，为了实现计算器的业务，我们还需要制作一个获取栈顶部数据且不使该数据被抹除的方法(弹栈了但没完全弹栈，只是试探性地“窥探”栈顶部的数据)，该静态方法只会使用到符号栈中，用于判断符号栈的“下一个”准备弹栈的符号的优先级来进行计算。

1
2
3

public double getPeekData() {
        return this.arrayStack[this.index];
    }

做计算器吧！

你一定好奇，这个鬼东西怎么能和计算器扯上联系？

试想实现一个用户输入一个字符串:”1+93-8”，然后程序对其进行数学运算后输出计算结果。(先运算93再运算+1和-8)

ne？是不是听起来十分复杂。没关系，通过栈的特性，我们可以让思路简化。

首先开辟一个栈用于存储数字、再开辟一个栈用于存储符号，只要我们把数字、符号分门别类的存储好，安排上运算优先级逻辑，对两个栈进行实时入栈弹栈即可！

既然要做数学运算，加减乘除的优先级肯定得考虑，那么具体要怎么表示它们的优先级呢？我们可以用boolean类型来区分，即true为乘除，false为加减，不过这样考虑优先级可扩展性就显得较低了，我们可以考虑用一个整数来表示优先级，整数越大，优先级越高，咱们新开一个工具类，取个名字叫StackUtil，在里面写上这样的代码

public static int getPriority(char i){
    if(i == '+' || i == '-'){
        return 0;
    }
    if(i == '*' || i == '/'){
        return 1;
    }
    return -1;
}

well, 这样就可以取得优先级了！接着我们可以对StackUtil这一工具类里添加一些功能，例如计算

public static double calculate(double num1, double num2, int type){//前两个double参数从数字栈中取出，type从符号栈取出，这里使用int(ASCII码表示)，当然也可以使用char，只不过我们做的栈是double的栈，存储数字便显得方便了
    double sum = 0;
    switch (type){
        case '+':
            sum = num1 + num2;
            break;
        case '-':
            sum =  num2 - num1;//由于栈的特性是先进入的后出，后进入的先出，所以实际弹栈的顺序与我们输入的顺序是相反的，因此减和除需要反过来写
            break;
        case '*':
            sum =  num1 * num2;
            break;
        case '/':
            sum = num2 / num1;
            break;
        default:
            sum = 0;
    }
    return sum;
}

同时，我们还可以加上一个判断字符是否是数学运算符的方法

1
2
3

public static boolean isSymbol(char i){
    return i == '+' || i == '-' || i == '*' || i == '/';
}

好啦！😃铺垫全都做好了，接下来就是我们的重头戏了！

新开一个类，我们给他起个名字叫Calculator吧！

咱们先从简单的开始，接收用户输入的一个字符串，并将其“存储”进一个名为expression的字符串对象内

import java.util.Scanner;
public class Calculator {
    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);
        String expression = scanner.next();
        /*
         * 在这里创建俩栈对象，分别对其开辟10的大小(能一次性存储10个数据)
         * 别觉得10很小哦，实际上我们的计算是实时的，不是一股脑塞入所有数据，所以数字栈中一次性可能只会出现2~3个数据，符号栈可能出现1~2个数据，因此开辟10个数据的栈空间是完全有余的
        */
        StackObject numberStack = new StackObject(10);  //数字栈
        StackObject symbolStack = new StackObject(10);  //符号栈

拿到了用户给出的表达式，程序需要分析哪些是数字、哪些是符号，然后将他们分门别类地放进数字栈与符号栈，那么如何分析呢？

我们可以通过遍历字符串对象内的字符数组获取每一个字符，通过工具类中isSymbol静态方法判断是否是符号，如果所遍历到的字符是符号的话就进入符号栈，如果不是符号的话就叠加到一个临时字符串对象内，等遇到下一个符号时，将临时字符串对象转化为双精度浮点数存入数字栈中，并清空临时字符串对象以便下次使用。

在存入数字与符号时，我们需要进行实时的运算，举个栗子：12+2*3

在计算这个表达式时，我们程序的运行步骤是:

1存入临时对象number中

2与number的值进行字符串拼接，此时number是”12”

检测到+是数学运算符，将number压入数字栈，并将+压入符号栈

继续向下遍历，发现2，此时number为”2”

发现下一位是*，将number的”2”压入数字栈

这个时候不能忙着计算，我们还得判断一下优先级，发现*的优先级是大于+的优先级的。那么我们就不能进行计算，需要等到乘号和”3”压栈后才可计算

所以*入栈，3入栈，

此时从数字栈中弹栈2次，符号栈中弹栈1次，分别得到2、3和*

使用我们工具类中的calculate方法，输入参数方可计算

得到2*3结果6，继续压栈数字栈

我们需要明确一个思路要点：

当符号栈中啥也没有时，数字直接压栈，但如果符号栈中有东西的话，我们需要用getPeekData方法(上文写的)来“窥探”符号栈顶部的一个符号判断优先级，如果新要入栈的符号的优先级≤原先的符号优先级的话，就先将原先的数字栈中弹出两个数据，符号栈中弹出一个数据，使用上文写的calculate方法进行计算，再将新符号入符号栈，运算结果进入数字栈

代码如下

String number = "";//临时存储数字用
int i = -1;
for (char c : expression.toCharArray()) {//获取expression对象的字符数组并遍历
    i++;//表示遍历到第几位了
    System.out.println(c);//输出当前遍历到的字符
    if(StackUtil.isSymbol(c)){
        if (!symbolStack.isEmpty()) {
            if (StackUtil.getPriority((char) symbolStack.getPeekData()) >= StackUtil.getPriority(c)) {//判断优先级
                double num1 = numberStack.pop();
                double num2 = numberStack.pop();
                int a = (int)symbolStack.pop();
                numberStack.push(StackUtil.calculate(num1, num2, a));
            }
        }
        System.out.println("运算符入栈");
        symbolStack.push(c);
    }else{
        number += c;//1+12+3
        if(!(expression.length() == i+1)) {//不是最后一位
            System.out.println(c+"下一位是"+expression.charAt(i+1));
            if (StackUtil.isSymbol(expression.charAt(i+1))) {//后一位是否是运算符
                numberStack.push(Integer.parseInt(number));//是的话
                System.out.println(number+"入栈");
                number = "";
                System.out.println(c+"的后一位是运算符");
            }
        }else{
            numberStack.push(Integer.parseInt(number));
            System.out.println("最后一位入栈"+number);
            number = "";

        }
    }

}

优先级计算结束了，最后符号栈中剩下的就只有加号\减号这类运算符，考虑到用户输入的表达式是变长的，我们使用while循环将符号栈弹空为止

while(!symbolStack.isEmpty()) {
    double num1 = numberStack.pop();
    double num2 = numberStack.pop();
    int a = (int)symbolStack.pop();
    numberStack.push(StackUtil.calculate(num1, num2, a));
}

System.out.println("计算结果为" + numberStack.pop());

至此，计算结束。

程序IO

输入

1	12+3-6*3+8/3

输出

1
1下一位是2
2
2下一位是+
12入栈
2的后一位是运算符
+
运算符入栈
3
3下一位是-
3入栈
3的后一位是运算符
-
运算符入栈
6
6下一位是*
6入栈
6的后一位是运算符
*
运算符入栈
3
3下一位是+
3入栈
3的后一位是运算符
+
运算符入栈
8
8下一位是/
8入栈
8的后一位是运算符
/
运算符入栈
3
最后一位入栈3
计算结果为-5.666666666666668

Process finished with exit code 0

代码一览

StackObject.java

package hugh;


import java.util.Arrays;

public class StackObject {
    double[] arrayStack;
    int stackSize;
    int index = -1;
    public StackObject(int stackSize){
        this.stackSize = stackSize;
        arrayStack = new double[stackSize];
    }
    public void push(double data){
        if(isFull()){
            throw new RuntimeException("错误：栈已满");
        }else {
            index++;
            arrayStack[index] = data;
        }
    }
    public String toString(){
        return Arrays.toString(arrayStack);
    }
    public double pop(){
        if(isEmpty()){
            throw new RuntimeException("错误：栈已空");
        }else {
            double data = arrayStack[index];
            index--;
            return data;
        }
    }
    public boolean isEmpty(){
        return index == -1;
    }
    public boolean isFull(){
        return index == (stackSize - 1);
    }
    public double getPeekData(){
        return arrayStack[index];
    }
}

StackUtil.java

package hugh;

public class StackUtil {
    public static boolean isPal(String text){
        StackObject stackObject = new StackObject(10);
        for (char c : text.toCharArray()) {
            stackObject.push(c);
        }
        StringBuilder data = new StringBuilder();
        while(!stackObject.isEmpty()){
            data.append((char) stackObject.pop());
        }
        if(data.toString().equals(text)){
            return true;
        }else{
            return false;
        }
    }
    public static double calculate(double num1, double num2, int type){
        double sum = 0;
        switch (type){
            case '+':
                sum = num1 + num2;
                break;
            case '-':
                sum =  num2 - num1;
                break;
            case '*':
                sum =  num1 * num2;
                break;
            case '/':
                sum = num2 / num1;
                break;
            default:
                sum = 0;
        }
        return sum;
    }
    public static boolean isSymbol(char i){
        return i == '+' || i == '-' || i == '*' || i == '/';
    }
    public static int getPriority(char i){
        if(i == '+' || i == '-'){
            return 0;
        }
        if(i == '*' || i == '/'){
            return 1;
        }
        return -1;
    }
}

Calculator.java

package hugh;

import java.util.Scanner;

public class Calculator{
    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);
        String expression = scanner.next();
        //String expression = "32*13+1";
        StackObject numberStack = new StackObject(100);
        StackObject symbolStack = new StackObject(100);

        String number = "";
        int i = -1;
        for (char c : expression.toCharArray()) {
            i++;
            System.out.println(c);
            if(StackUtil.isSymbol(c)){
                if (!symbolStack.isEmpty()) {
                    if (StackUtil.getPriority((char) symbolStack.getPeekData()) >= StackUtil.getPriority(c)) {
                        double num1 = numberStack.pop();
                        double num2 = numberStack.pop();
                        int a = (int)symbolStack.pop();
                        numberStack.push(StackUtil.calculate(num1, num2, a));
                    }
                }
                System.out.println("运算符入栈");
                symbolStack.push(c);
            }else{
                number += c;//1+12+3
                if(!(expression.length() == i+1)) {//不是最后一位
                    System.out.println(c+"下一位是"+expression.charAt(i+1));
                    if (StackUtil.isSymbol(expression.charAt(i+1))) {//后一位是否是运算符
                        numberStack.push(Integer.parseInt(number));//是的话
                        System.out.println(number+"入栈");
                        number = "";
                        System.out.println(c+"的后一位是运算符");
                    }
                }else{
                    numberStack.push(Integer.parseInt(number));
                    System.out.println("最后一位入栈"+number);
                    number = "";

                }
            }
            //System.out.println(c);
        }
        //System.out.println(numberStack.toString());
        while(true){
            if (symbolStack.isEmpty()) {
                break;
            }else{
                double num1 = numberStack.pop();
                double num2 = numberStack.pop();
                int a = (int)symbolStack.pop();
                numberStack.push(StackUtil.calculate(num1, num2, a));
            }
        }

        System.out.println(numberStack.pop());
    }
}