LeetCode-224.Basic Calculator

题目

Implement a basic calculator to evaluate a simple expression string.
The expression string may contain open ( and closing parentheses ), the plus + or minus sign -, non-negative integers and empty spaces .

样例

Input: "1 + 1"
Output: 2

Input: " 2-1 + 2 "
Output: 3

Input: "(1+(4+5+2)-3)+(6+8)"
Output: 23 

题目分析

难度: Hard(其实是个水题)

题意

实现一个简单计算器，给出的表达式只包含+ - ( )和空格。两个数/运算符之间可能有空格，也可能没有空格。

非常经典的简单问题，但对于没有接触过的人来说，还是有一定难度的，难点在于括号处理和数字、运算符、括号的解析。

思路

表达式解析

因为空格出现的位置不确定，不如直接将所有空格去掉。

假设我们现在只需要处理没有括号的情况。

我们用一个index不断在表达式中前进。用一个变量nowVal记录数字之和。若当前为符号，则将符号记录下来。若当前为数字，则不断向后查找相连的所有数字，找出这段数字的区间，解析它。解析出数字后，若之前的符号为+，则将数字加到nowVal上，反之减去。

括号处理

遇到括号时，我们需要先计算出括号中所有数字的和。遇到左括号时，我们可以将当前的nowVal和括号前的运算符压到栈中去。然后清空nowVal，开始计算括号中的值和遇到右括号时，我们已得到了所有信息：整个括号左侧的数(在栈顶)，括号左侧的运算符(在栈顶)，括号的值(nowVal)。

这时将两数求值即可。

代码

import java.util.Stack;

class Solution {
    private static final int ADD = -1;
    private static final int SUBTRACT = -2;
    private static final int LEFT = -3;
    private static final int RIGHT = -4;
    private String str;
    private int index = 0;

    public int calculate(String s) {
        str = s.replaceAll(" ", "");
        Stack<Integer> numStk = new Stack<>();
        Stack<Integer> operStk = new Stack<>();
        int nowVal = 0;
        int last = ADD;
        
        while (hasNext()) {
            int now = getNext();
            if (now == ADD) {
                last = ADD;
            } else if (now == SUBTRACT) {
                last = SUBTRACT;
            } else if (now == LEFT) {
                numStk.push(nowVal);
                operStk.push(last);
                last = ADD;
                nowVal = 0;
            } else if (now == RIGHT) {
                if (operStk.pop() == ADD) {
                    nowVal = numStk.pop() + nowVal;
                } else {
                    nowVal = numStk.pop() - nowVal;
                }
            } else {
                if (last == ADD) {
                    nowVal += now;
                } else {
                    nowVal -= now;
                }
            }
        }
        return nowVal;
    }

    private boolean hasNext() {
        return index < str.length();
    }

    private int getNext() {
        int chr = str.charAt(index++);
        if (chr == '(') {
            return LEFT;
        } else if (chr == ')') {
            return RIGHT;
        } else if (chr == '+') {
            return ADD;
        } else if (chr == '-') {
            return SUBTRACT;
        }
        int startIndex = index - 1;
        while (index < str.length() && str.charAt(index) >= '0' && str.charAt(index) <= '9') {
            index++;
        }
        return Integer.parseInt(str.substring(startIndex, index));
    }
}