224. Basic Calculator

https://leetcode.com/problems/basic-calculator/

Given a string s representing a valid expression, implement a basic calculator to evaluate it, and return the result of the evaluation.

Note: You are not allowed to use any built-in function which evaluates strings as mathematical expressions, such as eval().

Example 1:

Input: s = "1 + 1"
Output: 2

Example 2:

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

Example 3:

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

Constraints:

• 1 <= s.length <= 3 * 105

• s consists of digits, '+', '-', '(', ')', and ' '.

• s represents a valid expression.

• '+' is not used as a unary operation (i.e., "+1" and "+(2 + 3)" is invalid).

• '-' could be used as a unary operation (i.e., "-1" and "-(2 + 3)" is valid).

• There will be no two consecutive operators in the input.

• Every number and running calculation will fit in a signed 32-bit integer.

Solution:

Version 1: JAVA Deque Rescursion 双向队列模拟栈

class Solution {
    public int calculate(String s) {
        Deque<Character> deque = new LinkedList<>();
        for(int i = 0; i < s.length(); i++){
            //入队的时候就把空格排除在外，省的接下来再额外判断
            if(s.charAt(i) != ' '){
                deque.addLast(s.charAt(i));
            }
        }
        return helper(deque);
    }
    private int helper(Deque<Character> deque){ 
        Deque<Integer> stack = new LinkedList<>();
        char sign = '+';
        int num = 0;
        while(deque.size() > 0){
            char c = deque.removeFirst();
            if(isdigit(c)){
                num = num * 10 + (c - '0');
            }
            if(c == '('){
                num = helper(deque);
            }
            if(!isdigit(c) || deque.size() == 0){
                if(sign == '+'){
                    stack.addLast(num);
                }else if(sign == '-'){
                    stack.addLast(-num);
                }else if(sign == '*'){
                    int pre = stack.removeLast();
                    stack.addLast(pre*num);
                }else if(sign == '/'){
                    int pre = stack.removeLast();
                    stack.addLast(pre/num);
                }
                num = 0;
                sign = c;
            }
            if(c == ')'){
                break;
            }
        }
        int res = 0;
        while(stack.size() > 0){
            int top = stack.removeLast();
            res += top;
        }
        return res;
    }
    private boolean isdigit(char c){
        if(c >= '0' && c <= '9'){
            return true;
        }
        return false;
    }
}

Just + - Version : (LC 224) 递归版

class Solution {
    public int calculate(String s) {
        Deque<Character> queue = new LinkedList<>();
        for(int i = 0; i< s.length(); i++)
        {
            if(s.charAt(i) != ' ')
            {
                queue.addLast(s.charAt(i));
            }
        }
        return helper(queue);
    }
    
    public int helper(Deque<Character> queue)
    {
        Deque<Integer> stack = new LinkedList<>();
        int num = 0;
        char preSign = '+';
        while(queue.size() > 0)
        {
            char current = queue.removeFirst();
            
            if(isNumber(current))
            {
                num = num * 10 + (current - '0');
            }
            if(current == '(')
            {
                num = helper(queue);
            }
            if(!isNumber(current) || queue.size() == 0)
            {
                switch(preSign)
                {
                    case '+': stack.push(num); break;
                    case '-': stack.push(-num); break;
                }
                preSign = current;
                num = 0;
            }
            if(current == ')') break;
        }
        
        int res = 0;
        while(stack.size() > 0)
        {
            res += stack.removeLast();
        }
        return res;
        
    }
    
    public boolean isNumber(char c)
    {
        return c >= '0' && c <= '9';
    }
}

Version 2: 非递归

这道题目只有非负整数加减, 比较简单, 不过也完全可以按照完整的含有加减乘除等运算的中缀表达式与后缀表达式之间的转换来做.

而中缀表达式与后缀表达式之间的转换可以很容易搜索到, 这里不多赘述. 这里只讲针对于该题的做法:

我们需要三个变量和一个栈: number表示当前的操作数, sign表示当前的操作数应该被加还是被减, result表示结果.

初始number, result = 0, sign = 1, 开始遍历字符串:

• 碰到数字则追加到number尾端

• 碰到加号说明上一个数字已经完全被计算至number, 这时应该把number * sign加到result中, 然后把sign置为1 (因为当前碰到了加号)

• 碰到减号, 同上, 不同的在于最后要把sign置为-1

• 碰到左括号, 说明这时要优先出右边的表达式, 需要将result和sign压入栈中(注意, 此时的sign表示的是这个括号内的表达式应该被result加上还是减去), 然后初始化result和sign, 准备计算括号内的表达式

• 碰到右括号, 说明一个括号内的表达式被计算完了, 此时需要从栈中取出该括号之前的sign和result, 与当前的result相加运算 (注意, 是原来的result + sign * 当前result)

注意, 一个合法的表达式, 左括号之前一定不会是数字, 右括号之前一定是一个数字. 所以碰到右括号不要忘了先把number * sign加到当前result里.

以及, 循环结束后number可能还有数字, 需要加到result里. (比如"1+2"这样的表达式, 2并不会在循环内被加到结果中)

public class Solution {
    /**
     * @param s: the given expression
     * @return: the result of expression
     */
    public int calculate(String s) {
        Stack<Integer> stack = new Stack<Integer>();
        int result = 0;
        int number = 0;
        int sign = 1;
        for (int i = 0; i < s.length(); i ++) {
            char c = s.charAt(i);
            if (Character.isDigit(c)) {
                number = 10 * number + (int)(c - '0');
            } else if (c == '+') {
                result += sign * number;
                number = 0;
                sign = 1;
            } else if (c == '-') {
                result += sign * number;
                number = 0;
                sign = -1;
            } else if (c == '(') {
                //we push the result first, then sign;
                stack.push(result);
                stack.push(sign);
                //reset the sign and result for the value in the parenthesis
                sign = 1;
                result = 0;
            } else if (c == ')') {
                result += sign * number;
                number = 0;
                result *= stack.pop();    //stack.pop() is the sign before the parenthesis
                result += stack.pop();   //stack.pop() now is the result calculated before the parenthesis

            }
        }
        if (number != 0) {
            result += sign * number;
        }
        return result;
    }
}