表达式计算

7546 字
19 分钟

乘上与平时相反的列车，为了去看曾未见过的风景

表达式计算是程序设计中常见的问题，通常考察我们对于栈的理解和运用。但是在表达式计算的题目中，经常出现各种细节的改变，如

  • 是否考察一元运算符”-”。
  • 是否考虑括号 ()。
  • 是否考虑乘除高级运算。

有时一个小小的条件改变就让我们变得手足无措，因此本博客将从易到难，带你体验两种不同的设计方法，来解决此类题目。

  • 延迟计算法
  • 双栈法

简单加减运算

我们首先通过一种最简单的情况来理解两种方法的核心思想，题目：

要求：实现只包含线性加减运算表达式的求值。

示例：1 + 1 + 2 - 3 + 4 - 5

延迟计算法

顾名思义，延迟计算法的计算是延迟完成的。我们将在读取到下一个运算符时，才进行上一个运算符及其操作数的运算。

核心思路如下：

  1. 维护一个全局计算结果 result和一个当前的符号 sign(+1或 -1)
  2. 从左到右遍历字符串。
  3. 遇到数字，将他累加的result中。(result = sign * currentNumber)
  4. 遇到 +或 -，跟新 sign(1表示加， -1表示减)
public class Example1{

    int i = 0;

    public int calculate(String s) {
        int result = 0;
        int currnetNumber = 0;
        int sign = 1;

        while(i < s.length()){
            if(Character.isDigit(s.charAt(i))){
                currnetNumber = currnetNumber * 10 + (s.charAt(i) - '0');
            }
            else if(s.charAt(i) == '+'){
                result += sign * currnetNumber;
                sign = 1;
                currnetNumber = 0;
            }
            else if(s.charAt(i) == '-'){
                result += sign * currnetNumber;
                sign = -1;
                currnetNumber = 0;
            }
            i++;
        }

        return result;
    }

    public static void main(String[] args) {
        Example1 s = new Example1();
        System.out.println(s.calculate("1 + 2 - 3- 5 + 1"));
    }
}

并且我们发现延迟计算方法天然的支持处理一元运算符”-“的问题。因为我们几乎将每个运算符都当作一个一元运算符来处理。

我们将整个表达式视作一些有符号数的相加运算。比如 -1+1-2

程序处理时将视为：(-1)+1+(-2)。

双栈法

双栈法的特点是创建两个栈：

  • 数字栈：只存放数字
  • 符号栈：只存放运算符号

数字栈用于压入数字，符号栈压入符号。每读取一对数字和一个操作符后就进行一次计算，从左向右计算。

算法流程：

  1. 初始化两个栈
  2. 从左到右遍历表达式
  3. 遇到数字：解析出完整数字，压入 nums
  4. 遇到操作符：将操作符入栈。
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Set;

public class Example {

    static Set<Character> opsTable = new HashSet<>();
    static {
        opsTable.add('+');
        opsTable.add('-');
    }

    public int calculate(String s){
        LinkedList<Integer> nums = new LinkedList<>();
        LinkedList<Character> ops = new LinkedList<>();
        int i = 0;
        while(i < s.length()){
            if(Character.isDigit(s.charAt(i))){
                int num = 0;
                while(i < s.length() && Character.isDigit(s.charAt(i))){
                    num = num*10 + s.charAt(i) - '0';
                    i++;
                }
                nums.push(num);
            }
            else if(opsTable.contains(s.charAt(i))){
                if(i == 0 && s.charAt(i) == '-'){
                    nums.push(0);
                }
                while(!ops.isEmpty()){
                    applyOp(nums, ops);
                }
                ops.push(s.charAt(i));
                i++;
            }
            else{
                i++;
            }
        }
        while (!ops.isEmpty()) {
            applyOp(nums, ops);
        }
        return nums.pop();
    }

    private void applyOp(LinkedList<Integer> nums, LinkedList<Character> ops){
        int num2 = nums.pop();
        int num1 = nums.pop();
        char op = ops.pop();
        switch (op) {
            case '+':
                nums.push(num1 + num2);            
                break;
            case '-':
                nums.push(num1 - num2);
                break;
            default:
                break;
        }
    }

    public static void main(String[] args) {
        Example s = new Example();
        System.out.println(s.calculate(" 2-1 + 2 "));
    }
}

双栈发并不能天然的支持单元运算符’-‘，需要我们特殊处理。我们将 -a转化为 0-a的形式。

这是应为双栈法的处理过程将每个运算符都当作二元运算来处理。每次运算都是两个数进行运算，逐渐和二为一。

如此简单的情况下，可能看不出来双栈法的好处，但是双栈法其实是实现计算器最经典、最强大的标准算法之一。

带括号加减表达式

224. 基本计算器 - 力扣（LeetCode）

1760336450189

1760336623329

接下来我们来完成leetcode这个题目，该题被标记为困难，但是只要理解上面的两种算法，要解决该题并不困难。

延迟计算

延迟计算方法是这一题的官方题解。因为该题要求考虑一元运算符，且不考虑乘除运算。

在不考虑乘除时，我们可以不使用递归。流程如下：

  • 状态：result(当前总和),sign(下一个符号)
  • 遇到 (：把result和sign这两个数值压入栈。然后重置 result = 0, sign = 1重新开始计算。
  • 遇到 )：完成括号内的计算得到 currentResult。然后从栈中弹出之前的 result和 sign，进行 result = result + sign * currentResult。

但是为了铺垫接下来再增加乘法运算，所以此处我使用递归的方法，流程如下：

  • 遇到 (：令 currentNum = calculate(s)
  • 遇到 )：跳出循环，将值返回给上层。
public class Example1{

    int i = 0;

    public int calculate(String s) {
        int result = 0;
        int currnetNumber = 0;
        int sign = 1;

        while(i < s.length()){
            if(Character.isDigit(s.charAt(i))){
                currnetNumber = currnetNumber * 10 + (s.charAt(i) - '0');
                i++;
            }
            else if(s.charAt(i) == '+'){
                result += sign * currnetNumber;
                sign = 1;
                currnetNumber = 0;
                i++;
            }
            else if(s.charAt(i) == '-'){
                result += sign * currnetNumber;
                sign = -1;
                currnetNumber = 0;
                i++;
            }
            else if(s.charAt(i) == '('){
                i++;
                currnetNumber = calculate(s);
            }
            else if(s.charAt(i) == ')'){
                result += sign * currnetNumber;
                currnetNumber = 0;
                i++;
                break;
            }
            else
                i++;
        }
        result += sign*currnetNumber;
        return result;
    }

    public static void main(String[] args) {
        Example1 s = new Example1();
        System.out.println(s.calculate("(1+(4+5+2)-3)+(6+8)"));
    }
}

双栈法

双栈法要将括号当作栈中的分割符，每次计算不能越过正括号 (，在遇到反括号 )时，必须计算两个括号间的所有运算。

  • 遇到 (：将 (压入符号栈
  • 遇到 )：进行运算，直到 (在符号栈栈顶。最后弹出 (。
  • 一元运算符：必须跳过空格去查找上一个字符是不是 (，或 i==0
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Set;

public class Example {

    static Set<Character> opsTable = new HashSet<>();
    static {
        opsTable.add('+');
        opsTable.add('-');
    }

    public int calculate(String s){
        LinkedList<Integer> nums = new LinkedList<>();
        LinkedList<Character> ops = new LinkedList<>();
        int i = 0;
        while(i < s.length()){
            if(s.charAt(i) == ' '){
                i++;
                continue;
            }
            if(Character.isDigit(s.charAt(i))){
                int num = 0;
                while(i < s.length() && Character.isDigit(s.charAt(i))){
                    num = num*10 + s.charAt(i) - '0';
                    i++;
                }
                nums.push(num);
            }
            else if(s.charAt(i) == '('){
                ops.push('(');
                i++;
            }
            else if(s.charAt(i) == ')'){
                while(ops.peek()!= '('){
                    applyOp(nums, ops);
                }
                ops.pop();
                i++;
            }
            else if(opsTable.contains(s.charAt(i))){
                // 检查是否为一元负号
                // 条件：当前是第一个字符，或者前一个字符不是数字也不是右括号
                boolean isUnary = false;
                if (s.charAt(i) == '-') {
                    int prev_i = i - 1;
                    // 跳过前面的空格
                    while(prev_i >= 0 && s.charAt(prev_i) == ' ') {
                        prev_i--;
                    }
                    if (prev_i < 0 || (s.charAt(prev_i) != ')' && !Character.isDigit(s.charAt(prev_i)))) {
                       isUnary = true;
                    }
                }

                if (isUnary) {
                    nums.push(0);
                }
          
                while(!ops.isEmpty() && ops.peek() != '('){
                    applyOp(nums, ops);
                }
                ops.push(s.charAt(i));
                i++;
            }
            else{
                i++;
            }
        }
        while (!ops.isEmpty()) {
            applyOp(nums, ops);
        }
        return nums.pop();
    }

    private void applyOp(LinkedList<Integer> nums, LinkedList<Character> ops){
        int num2 = nums.pop();
        int num1 = nums.pop();
        char op = ops.pop();
        switch (op) {
            case '+':
                nums.push(num1 + num2);          
                break;
            case '-':
                nums.push(num1 - num2);
                break;
            default:
                break;
        }
    }

    public static void main(String[] args) {
        Example s = new Example();
        System.out.println("2-(5-6) = " + s.calculate("2-(5-6)")); // 应该输出 3
        System.out.println("1-( -2) = " + s.calculate("1-(   -2)")); // 应该输出 3
    }
}

高级运算符乘法

除法会导致计算过程中出现浮点数，所以我们通常只考察乘法，以确保数据类型的一致性。

我们来看看牛客中的这道题。在加减括号中增加了运算符乘法。不过不用考虑一元运算符”-“。但是我们以下的代码都是支持一元运算符”-“的。

1760342960954

延迟计算法

对于有高优先级的表达式，不能直接使用result进行简单的线性相加。我们必须使用一个栈，将所有需要相加的数都压入栈中。如果遇到乘法，则立即计算，将所有相连的乘法运算最终计算为一个数。则最后栈中只剩下所有需要相加的数。

步骤：

  1. 遇到 *：弹出刚刚入栈的数字，赋值给symbol。

解释：1 + 2 * 5 * 3：

之前的延迟计算法中，sign通过1和-1表示加减，这里的加减同时可以理解为：+1*a,+(-1)*a

即，加上a的一倍，或加上a的负一倍。

当我们读取字符 *时，我们将2赋值给Symbol。则可以表示为加上5的2倍。

import java.util.HashSet;
import java.util.LinkedList;
import java.util.Set;

class Solution {

    static Set<Character> operator = new HashSet<>();
    static{
        operator.add('+');
        operator.add('-');
        operator.add('*');
    }
    int i = 0;

    public int calculate(String s) {
        LinkedList<Integer> numStack = new LinkedList<>();
        numStack.push(0);
        int currnetNumber = 0;
        int symbol = 1;
        while(i < s.length()){
            if(Character.isDigit(s.charAt(i))){
                currnetNumber = currnetNumber*10 + s.charAt(i) - '0';
                i++;
            }
            else if(operator.contains(s.charAt(i))){
                numStack.push(symbol * currnetNumber);
                if(s.charAt(i) == '+'){
                    symbol = 1;
                }
                else if(s.charAt(i) == '-'){
                    symbol = -1;
                }
                else if(s.charAt(i) == '*'){
                    symbol = numStack.pop();
                }
                currnetNumber = 0;
                i++;
            }
            else if(s.charAt(i) == '('){
                i++;
                currnetNumber = symbol*calculate(s);
                symbol = 1;
            }
            else if(s.charAt(i) == ')'){
                i++;
                break;
            }
            else{
                i++;
            }
        }
        numStack.push(symbol * currnetNumber);
        int result = 0;
        while(!numStack.isEmpty()){
            result += numStack.pop();
        }
        return result;
    }

    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.calculate("(2*(3-4))*5"));
    }
}

双栈法

双栈法的拓展性很好，也就是程序的解耦性很好。添加乘法运算只需添加很少的代码。

import java.util.HashSet;
import java.util.LinkedList;
import java.util.Set;

public class Solution {

    static Set<Character> opsTable = new HashSet<>();
    static {
        opsTable.add('+');
        opsTable.add('-');
        opsTable.add('*');
    }

    public int solve(String s){
        LinkedList<Integer> nums = new LinkedList<>();
        LinkedList<Character> ops = new LinkedList<>();
        int i = 0;
        while(i < s.length()){
            if(s.charAt(i) == ' '){
                i++;
                continue;
            }
            if(Character.isDigit(s.charAt(i))){
                int num = 0;
                while(i < s.length() && Character.isDigit(s.charAt(i))){
                    num = num*10 + s.charAt(i) - '0';
                    i++;
                }
                nums.push(num);
            }
            else if(s.charAt(i) == '('){
                ops.push('(');
                i++;
            }
            else if(s.charAt(i) == ')'){
                while(ops.peek()!= '('){
                    applyOp(nums, ops);
                }
                ops.pop();
                i++;
            }
            else if(opsTable.contains(s.charAt(i))){
                // 检查是否为一元负号
                // 条件：当前是第一个字符，或者前一个字符不是数字也不是右括号
                boolean isUnary = false;
                if (s.charAt(i) == '-') {
                    int prev_i = i - 1;
                    // 跳过前面的空格
                    while(prev_i >= 0 && s.charAt(prev_i) == ' ') {
                        prev_i--;
                    }
                    if (prev_i < 0 || (s.charAt(prev_i) != ')' && !Character.isDigit(s.charAt(prev_i)))) {
                       isUnary = true;
                    }
                }
                if (isUnary) {
                    nums.push(0);
                }
                while(!ops.isEmpty() && ops.peek() != '(' && precedence(ops.peek()) >= precedence(s.charAt(i)) ){
                    applyOp(nums, ops);
                }
                ops.push(s.charAt(i));
                i++;
            }
            else{
                i++;
            }
        }
        while (!ops.isEmpty()) {
            applyOp(nums, ops);
        }
        return nums.pop();
    }
  
    private void applyOp(LinkedList<Integer> nums, LinkedList<Character> ops){
        int num2 = nums.pop();
        int num1 = nums.pop();
        char op = ops.pop();
        switch (op) {
            case '+':
                nums.push(num1 + num2);              
                break;
            case '-':
                nums.push(num1 - num2);
                break;
            case '*':
                nums.push(num1*num2);
                break;
            default:
                break;
        }
    }

    private int precedence(char c){
        if(c == '*' || c == '/')
            return 2;
        if(c == '+' || c == '-')
            return 1;
        return 0;
    }

    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println( s.solve("(2*(3-4))*5"));
    }
}