Formatted question description: https://leetcode.ca/all/772.html

772. Basic Calculator III

Level

Hard

Description

Implement a basic calculator to evaluate a simple expression string.

The expression string contains only non-negative integers, +, -, *, / operators, open ( and closing parentheses ) and empty spaces ` `. The integer division should truncate toward zero.

You may assume that the given expression is always valid. All intermediate results will be in the range of [-2147483648, 2147483647].

Some examples:

"1 + 1" = 2

" 6-4 / 2 " = 4

"2*(5+5*2)/3+(6/2+8)" = 21

"(2+6* 3+5- (3*14/7+2)*5)+3"=-12

Note: Do not use the eval built-in library function.

Solution

Three steps to evaluate a simple expression string are reformat the expression string, convert the infix expression to postfix expression, and evaluate the postfix expression.

Step 1: Reformat the expression string. Remove all the empty spaces. Remove all the empty spaces, and if a minus sign - is at the beginning of the expression string or is just after an open parenthesis (, then add a number zero 0 before the minus sign.

Step 2: Convert the infix expression to postfix expression. The given expression string is an infix expression, and it is difficult to evaluate an infix expression directly, so it is necessary to convert the infix expression to postfix expression. For each character in the infix expression string, if the character is a digit, then generate the number from one or more consecutive digits, otherwise separate the operator. After numbers and operators are separated, convert the infix expression to postfix expression. Use a stack to store operators. Loop over the infix expression from start to end. If the current element is a number, append it to the postfix expression. If the current element is an operator, then consider the precedence of the current operator and the operator at the top of the stack, where * and / have a higher precedence than + and -.

While the current operator’s precedence is equal to or lower than the precedence of the operator at the top of the stack, pop the operators from the stack and append them to the postfix expression (the same order as the order that they are popped), until the stack is empty or the top of the stack is an operator that has a lower precedence than the current operator. Push the current operator into the stack.

The case for open and close parentheses are different from other operators. If an open parenthesis is not in the stack yet, the precedence of the open parenthesis is higher than any other operators. If an open parenthesis is in the stack, the precedence of the open parenthesis is lower than any other operators, and an open parenthesis in the stack is popped only if a close parenthesis is met. Concretely, the logic works as follows. If the current element is an open parenthesis, then push it into the stack. If the current element is a close parenthesis, then pop all signs from the stack and append them to the postfix expression (the same order as the order that they are popped), until the top of the stack is an open parenthesis, and pop the open parenthesis at the top of the stack.

Finally, if the stack is not empty, then pop all plus signs and minus signs from the stack and append them to the postfix expression (the same order as the order that they are popped).

Step 3: Evaluate the postfix expression. Use a stack to store numbers. Loop over the postfix expression from start to end. If the current element is a number, push it into the stack. If the current element is an operator, then pop two numbers and do the corresponding operation, and push the result number into the stack. Finally, there should be only one number in the stack, which is the result of the expression. Pop the stack and return the result.

  • public class Basic_Calculator_III {
    
    
        // ref: http://buttercola.blogspot.com/2019/03/leetcode-772-basic-calculator-iii.html
        class Solution {
            public int calculate(String s) {
                if (s == null || s.length() == 0) {
                    return 0;
                }
    
                // remove leading and trailing spaces and white spaces.
                //
                s = s.trim().replaceAll("[ ]+", "");
    
                if (s == null || s.length() == 0) {
                    return 0;
                }
    
                Stack<Character> opStack = new Stack<>();
                Stack<Integer> numStack = new Stack<>();
    
                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 + Character.getNumericValue(s.charAt(i));
                            i++;
                        }
                        numStack.push(num);
                    } else {
                        char op = s.charAt(i);
                        if (opStack.isEmpty()) {
                            opStack.push(op);
                            i++;
                        } else if (op == '+' || op == '-') {
                            char top = opStack.peek();
                            if (top == '(') {
                                opStack.push(op);
                                i++;
                            } else {
                                calculate(numStack, opStack);
                            }
                        } else if (op == '*' || op == '/') {
                            char top = opStack.peek();
                            if (top == '(') {
                                opStack.push(op);
                                i++;
                            } else if (top == '*' || top == '/') {
                                calculate(numStack, opStack);
                            } else if (top == '+' || top == '-') {
                                opStack.push(op);
                                i++;
                            }
                        } else if (op == '(') {
                            opStack.push(op);
                            i++;
                        } else if (op == ')') {
                            while (opStack.peek() != '(') {
                                calculate(numStack, opStack);
                            }
                            opStack.pop();
                            i++;
                        }
                    }
                }
    
                while (!opStack.isEmpty()) {
                    calculate(numStack, opStack);
                }
    
                return numStack.peek();
            }
    
            private void calculate(Stack<Integer> numStack, Stack<Character> opStack) {
                int num2 = numStack.pop();
                int num1 = numStack.pop();
    
                char op = opStack.pop();
    
                int ans = 0;
    
                switch(op) {
                    case '+':
                        ans = num1 + num2;
                        break;
                    case '-':
                        ans = num1 - num2;
                        break;
                    case '*':
                        ans = num1 * num2;
                        break;
                    case '/':
                        ans = num1 / num2;
                        break;
                }
    
                numStack.push(ans);
            }
        }
    }
    
  • // OJ: https://leetcode.com/problems/basic-calculator-iii/
    // Time: O(N)
    // Space: O(N)
    class Solution {
        stack<long> num;
        stack<char> op;
        unordered_map<char, int> priority{ {'+', 1}, {'-', 1}, {'*', 2}, {'/', 2} };
        void eval() {
            long b = num.top(); num.pop();
            char c = op.top(); op.pop();
            switch (c) {
                case '+': num.top() += b; break;
                case '-': num.top() -= b; break;
                case '*': num.top() *= b; break;
                case '/': num.top() /= b; break;
            }
        }
    public:
        int calculate(string s) {
            for (int i = 0, N = s.size(); i < N; ++i) {
                if (s[i] == ' ') continue;
                if (isdigit(s[i])) {
                    long n = 0;
                    while (i < N && isdigit(s[i])) n = n * 10 + s[i++] - '0';
                    --i;
                    num.push(n);
                } else if (s[i] == '(') op.push(s[i]);
                else if (s[i] == ')') {
                    while (op.top() != '(') eval();
                    op.pop();
                } else {
                    while (op.size() && op.top() != '(' && priority[op.top()] >= priority[s[i]]) eval();
                    op.push(s[i]);
                }
            }
            while (op.size()) eval();
            return num.top();
        }
    };
    
  • print("Todo!")
    

All Problems

All Solutions