双栈法求字符串算数表达式的运算结果

前情引入

今天助教给我们布置了一道题，是这样的：给一个算数表达式，要能运算出结果。不用太复杂，要求能支持加减乘除和小括号。听到这个，我马上就想到了用栈来做，因为在《算法导论》第四版中，在介绍栈的时候，用的就是这个例子。其实那本书我没看几页，但是栈那里刚好翻到过。

大概思路就是：利用栈FILO: first in last out，先进后出 的特性。用两个栈，一个栈用来存运算符（包括小括号），另一个栈用来存操作数，在需要运算的时候，就从符号栈中弹出一个运算符，从操作数栈中弹出两个操作数，将运算后的结果再压入栈中，到最后，操作数栈中只剩下一个操作数，就是表达式的结果。

具体细节

为了方便，规定每个符号和操作数之间用必须用空格分开，这样是为了方便从字符串中取出每个操作数。虽然不用空格隔开，也能取出操作数，但是太麻烦了，我们主要是为了理解这个算法的思想和熟悉栈这种数据结构。

步骤：

1. 创建一个操作数栈，一个运算符栈
2. 将这个字符串表达式按空格分开，用split方法
3. 遍历这个分割后的字符串数组，尝试对每个字符串转换成数字
   1. 如果转换成功，说明是一个数字，就将这个数字压入操作数栈。
   2. 如果转换失败，则说明是是加减乘除或小括号
      1. 如果是左小括号，则直接入栈，
      2. 如果是右边小括号，就需要将这个小括号中的表达式值计算出来
      3. 如果是加减乘除，需要判断符号栈中是否有运算符
         1. 如果栈中已经有运算符，就需要根据优先级判断是否需要计算
         2. 需要计算将弹出符号和操作数运算，并且将结果压入操作数栈
         3. 如果不需要计算，直接将运算符压入符号栈
      4. 没有运算符，直接将当前这个运算符压入符号栈
4. 最后再进行结尾操作，依次弹出符号和操作数，进行运算。当最后符号栈中没有符号时，操作数栈中会剩下最后一个数，这个数就是运算的结果。

代码展示

import java.util.Scanner;
import java.util.Stack;

/**
 * 一个工具类计算器，其calculate方法可以接受一个字符串表达式，返回表达式的结果
 *      代码没有简化、、、、很多冗余的地方
 */
//@SuppressWarnings("all")
public class Calculator1
{
    //public String expression;
    public static Stack<Double> numbers;
    public static Stack<String> operators;

    public static Double calculate(String expression)
    {
        //存放操作数的栈
        numbers = new Stack<>();
        //存放运算符的栈(包括小括号)
        operators = new Stack<>();
        //将表达式转为字符串数组（按空格分开）
        String[] strings = expression.split(" ");
        //遍历字符数组
        for (int i = 0; i < strings.length; i++)
        {
            //得到子串
            String each = strings[i];
            //提高变量的作用域，是需要数栈的操作数
            Double number;
            //尝试将字符串转数字
            try
            {
                //进行转换
                number = Double.parseDouble(each);
                //转换成功就压入数栈
                numbers.push(number);
            }
            //如果转换失败，说明是一个运算符或括号
            catch (NumberFormatException e)
            {
                //如果是左小括号，直接入符号栈，结束当前循环
                if ("(".equals(each))
                {
                    operators.push(each);
                    continue;
                }
                //如果是右边括号
                if (")".equals(each))
                {
                    String operator;
                    //一个死循环，每次从数栈中弹出两个操作数，从符号栈中弹出一个运算符，并进行计算，直到遇到左小括号
                    while (true)
                    {
                        operator = operators.pop();
                        if ("(".equals(operator))
                        { break; }
                        Double one = numbers.pop();
                        Double tow = numbers.pop();
                        if ("+".equals(operator))
                        { numbers.push(one+tow); }
                        if ("-".equals(operator))
                        { numbers.push(tow-one); }
                        if ("*".equals(operator))
                        { numbers.push(one*tow); }
                        if ("/".equals(operator))
                        { numbers.push(tow/one); }
                    }
                }
                //如果符号栈里的符号个数大于等于一个，就比较两个符号(当前的和栈顶的)的优先级别（这里需要分析一下）
                if (operators.size() >= 1)
                {
                    //如果当前优先级别小于符号栈里栈顶符号的优先级别，则从操作数栈弹出两个数，符号栈中弹出一个符号。
                    //注意：比较的时候，不要直接从符号栈中弹出符号，因为可能不进行运算
                    if (operatorClass(each) < operatorClass(operators.peek()))
                    {
                        Double one = numbers.pop();
                        Double tow = numbers.pop();
                        String operator = operators.pop();
                        if ("*".equals(operator))
                        { numbers.push(one*tow); }
                        if ("/".equals(operator))
                        { numbers.push(tow/one); }
                        if ("-".equals(operator))
                        { numbers.push(tow-one); }
                        if ("+".equals(operator))
                        { numbers.push(tow+one); }
                    }
                }
                //右边小括号不入栈
                if (!")".equals(each))
                { operators.push(each); }
            }
        }

        //最后的收尾工作
        while (operators.size() > 0)
        {
            Double one = numbers.pop();
            Double tow = numbers.pop();
            String operator = operators.pop();
            if ("+".equals(operator))
            { numbers.push(one+tow); }
            if ("-".equals(operator))
            { numbers.push(tow-one); }
            if ("*".equals(operator))
            { numbers.push(one*tow); }
            if ("/".equals(operator))
            { numbers.push(tow/one); }
        }
        return numbers.pop();
    }

    //判断运算符的等级
    public static int operatorClass(String operator)
    {
        if ("*".equals(operator) || "/".equals(operator))
        { return 2; }
        if ("+".equals(operator) || "-".equals(operator))
        { return 1; }
        if ("(".equals(operator) || ")".equals(operator))
        { return 0; }
        throw new RuntimeException("目前不支持此类此类操作符" + operator);
    }


    //测试
    public static void main(String[] args)
    {
        Scanner input = new Scanner(System.in);
        while (true)
        {
            System.out.println();
            System.out.println("每个数字和符号之间需要使用空格分开！");
            System.out.print("请输入算数表达式(Q/q退出)：");
            String s = input.nextLine();
            if ("Q".equals(s) || "q".equals(s))
            { break; }
            System.out.println("结果为："+calculate(s));
        }
    }
}

//测试用例                                                  结果
// 3 + 2 - 5                                               0.0
// ( 9 / 3 ) + ( 2 * 3 )                                   9.0
//  1 + 6 / 3 - 2                                          1.0
// 18 / ( 9 - 6 ) + 3                                      9.0
//  4.5 * ( 1.5 + 0.5 ) - ( 9 - 3.5 )                      3.5
// ( 7 - 20 / 5 ) + ( 33 - 17 )                            19.0
// 20 - ( 30 / ( 9 - 6 ) )                                 10.0

经过简单的测试，没有发现问题，不知道是否有隐藏的bug。

其实如果只看上面的步骤思路和代码，不一定好理解。用一个例子，结合代码或步骤走一遍就会好很多。

比如：18 / ( 9 - 6 ) + 3 。

1. 首先它会被拆成一个字符串数组{“18”,”/","(",“9”,"-",“6”,")","+",“3”}
2. 遍历这个字符串数组
3. “18” 转换成功，并且存入操作数栈。
4. “/” 转换失败，并且此时符号栈中没有符号，压入符号栈。
5. “(” 转换失败，直接压入符号栈中。
6. “9” 转换成功，压入操作数栈。
7. “-” 转换失败，此时符号栈中已经有"/“和”(“了，因为栈顶的符号时”("，它的优先级比"-"低，所以不运算，直接压入符号栈。
8. “6” 转换成功，压入操作数栈
9. “)” 转换失败，因为是右小括号，所以要将里面的表达式计算出来，直到左边小括号。
10. 从符号栈中弹出栈顶的"-"，从操作数栈中弹出两个操作数6和9，做减法之后再将结果3压入操作数栈，
11. 再从符号栈中弹出栈顶符号："("，结束当前循环。
12. 此时符号栈中："/ " 操作数栈： 18 3
13. 下一字符串，"+" 转换失败，此时符号栈中已经有一个"/“了，并且”/“的优先级比”+“要高。所以从符号栈中弹出”/"，从操作数栈中弹出3和18，做除法结果为6，并且将它压入操作数栈。再将"+"压入符号栈。
14. 此时，符号栈中："+"，操作数栈中：6
15. 下一个字符串，“3” 转换成功，压入操作数栈。
16. 收尾工作，从符号栈中弹出"+"，从操作数栈中弹出3和6，做加法运算之后为9，将其压入操作数栈。
17. 最后的结果就是操作数栈中的9。
    （double类型做运算的时候，应该带小数点）

优化

用到了三次，判断运算符和计算，将其抽取成一个方法。

import java.util.Scanner;
import java.util.Stack;

/**
 * 一个工具类计算器，其calculate方法可以接受一个字符串表达式，返回表达式的结果
 *      经过初步简化
 */
@SuppressWarnings("all")
public class Calculator2
{
    //public String expression;
    public static Stack<Double> numbers;
    public static Stack<String> operators;

    public static Double calculate(String expression)
    {
        //存放操作数的栈
        numbers = new Stack<>();
        //存放运算符的栈(包括小括号)
        operators = new Stack<>();
        //将表达式转为字符串数组（按空格分开）
        String[] strings = expression.split(" ");
        //遍历字符数组
        for (int i = 0; i < strings.length; i++)
        {
            //得到子串
            String each = strings[i];
            //提高变量的作用域，是需要数栈的操作数
            Double number;
            //尝试将字符串转数字。
            try
            {
                //进行转换
                number = Double.parseDouble(each);
                //转换成功就压入数栈
                numbers.push(number);
            }
            //如果转换失败，说明是一个运算符或括号
            catch (NumberFormatException e)
            {
                //如果是左小括号，直接入符号栈，结束当前循环
                if ("(".equals(each))
                {
                    operators.push(each);
                    continue;
                }
                //如果是右边括号
                if (")".equals(each))
                {
                    String operator;
                    //一个死循环，每次从数栈中弹出两个操作数，从符号栈中弹出一个运算符，并进行计算，直到遇到左小括号
                    while (true)
                    {
                        operator = operators.pop();
                        if ("(".equals(operator))
                        { break; }
                        calculate(numbers.pop(),numbers.pop(),operator,numbers);
                    }
                }
                //如果符号栈里的符号个数大于等于一个，就比较两个符号(当前的和栈顶的)的优先级别（这里需要分析一下）
                if (operators.size() >= 1)
                {
                    //如果当前优先级别小于符号栈里栈顶符号的优先级别，则从操作数栈弹出两个数，符号栈中弹出一个符号进行运算
                    //这里的临界情况，也可以将相同运算级别的运算符先进行运算，这样在最后的收尾时就会少一些工作。注意比较的时候不要弹栈
                    if (operatorClass(each) < operatorClass(operators.peek()))
                    { calculate(numbers.pop(),numbers.pop(),operators.pop(),numbers); }
                }
                //右边小括号不入栈
                if (!")".equals(each))
                { operators.push(each); }
            }
        }
        //最后的收尾工作，将符号栈中所有的符号弹出，并且计算。因为前面已经对优先级高的符号做了运算，所以到这里的一定是同级运算符
        while (operators.size() > 0)
        { calculate(numbers.pop(),numbers.pop(),operators.pop(),numbers); }
        return numbers.pop();
    }

    //判断运算符的等级
    public static int operatorClass(String operator)
    {
        if ("*".equals(operator) || "/".equals(operator))
        { return 2; }
        if ("+".equals(operator) || "-".equals(operator))
        { return 1; }
        //这里小括号的优先级最低的原因是：当符号栈中有一个以上的运算符时，需要进行等级比较并且运算。
        if ("(".equals(operator) || ")".equals(operator))
        { return 0; }
        throw new RuntimeException("目前不支持此类此类操作符" + operator);
    }

    //进行运算并且压如数栈的操作
    public static void calculate(Double one, Double tow, String operator, Stack<Double> numbers)
    {
        if ("+".equals(operator))
        { numbers.push(one+tow); }
        if ("-".equals(operator))
        { numbers.push(tow-one); }
        if ("*".equals(operator))
        { numbers.push(one*tow); }
        if ("/".equals(operator))
        { numbers.push(tow/one); }
    }


    //测试
    public static void main(String[] args)
    {
        Scanner input = new Scanner(System.in);
        while (true)
        {
            System.out.println();
            System.out.println("每个数字和符号之间需要使用空格分开！");
            System.out.print("请输入算数表达式(Q/q退出)：");
            String s = input.nextLine();
            if ("Q".equals(s) || "q".equals(s))
            { break; }
            System.out.println("结果为："+calculate(s));
        }
    }
}

//测试用例
// 3 + 2 - 5                                               0.0
// ( 9 / 3 ) + ( 2 * 3 )                                   9.0
//  1 + 6 / 3 - 2                                          1.0
// 18 / ( 9 - 6 ) + 3                                      9.0
//  4.5 * ( 1.5 + 0.5 ) - ( 9 - 3.5 )                      3.5
// ( 7 - 20 / 5 ) + ( 33 - 17 )                            19.0
// 20 - ( 30 / ( 9 - 6 ) )                                 10.0

经过简单的测试，没有发现问题，不知道是否有隐藏的bug。

本文地址：https://blog.csdn.net/ql_7256/article/details/107487296