Question

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

 227. Basic Calculator II

 Implement a basic calculator to evaluate a simple expression string.

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


 Example 1:

 Input: "3+2*2"
 Output: 7


 Example 2:

 Input: " 3/2 "
 Output: 1


 Example 3:

 Input: " 3+5 / 2 "
 Output: 5


 Note:
     You may assume that the given expression is always valid.
     Do not use the eval built-in library function.

 @tag-stack

Algorithm

Due to the operational priority, the measure we took is to use a stack to store the numbers

  • If the sign before the number is addition or subtraction, then push the current number onto the stack. Note that if it is a minus sign, add the opposite number of the current number, because subtraction is equivalent to adding an opposite number.
  • If the previous symbol is multiplication or division, then take a number from the top of the stack and the current number for multiplication or division, and then push the result onto the stack.

Then after completing the traversal, all the multiplications or divisions are completed, and all the numbers in the stack are added up to get the final result.

Code

Java

  • import java.util.Stack;
    
    public class Basic_Calculator_II {
    
        class Solution {
    
            // possible overflow
            public int calculate(String s) {
                if (s == null || s.length() == 0) {
                    return 0;
                }
    
                Stack<Integer> sk = new Stack<>();
    
                // always cache prev number and operator, if * or /, then compute result
                char prevOperator = '+';
                int prevNumber = 0;
    
                // 3+2*4+5
                for (int i = 0; i < s.length(); i++) {
                    char current = s.charAt(i);
    
                    if (current >= '0' && current <= '9') { // parse value
                        // it's a digit
                        prevNumber = prevNumber * 10 + (current - '0');
                    }
    
                    // find an operator, so check this operator's prev number and prev number's operator
                    if ((current < '0' && current != ' ') || i == s.length() - 1) {
                        // it's a operator
                        if (prevOperator == '+') { // @note: key is compare prev operator, not current operator
                            sk.push(prevNumber);
                        } else if (prevOperator == '-') {
                            sk.push(-1 * prevNumber);
                        } else if (prevOperator == '*' || prevOperator == '/') {
                            int tmp = (prevOperator == '*') ? sk.peek() * prevNumber : sk.peek() / prevNumber;
                            sk.pop();
                            sk.push(tmp);
                        } // else skip space
    
                        prevOperator = current;
                        prevNumber = 0; // if an operator triggering a calculation, reset prevNumber, because result pushed to stack already
                    }
                }
    
                int result = 0;
                while (!sk.empty()) { // before while, all vals in stack to be added. no * or /
                    result += sk.peek();
                    sk.pop();
                }
    
                return result;
            }
        }
    }
    
  • // OJ: https://leetcode.com/problems/basic-calculator-ii/
    // Time: O(N)
    // Space: O(N)
    class Solution {
        inline int priority(char op) {
            if (op == '\0') return 0;
            if (op == '+' || op == '-') return 1;
            if (op == '*' || op == '/') return 2;
            return 3;
        }
        vector<string> tokenize(string &s) {
            vector<string> ans;
            for (int i = 0, N = s.size(); i < N; ) {
                while (i < N && s[i] == ' ') ++i;
                if (i >= N) break;
                if (isdigit(s[i])) {
                    int j = i;
                    while (i < N && isdigit(s[i])) ++i;
                    ans.push_back(s.substr(j, i - j));
                } else ans.push_back(s.substr(i++, 1));
            }
            return ans;
        }
        void pushOps(vector<string> &ans, stack<string> &ops, string op = "") {
            while (ops.size() && priority(op[0]) <= priority(ops.top()[0])) {
                ans.push_back(ops.top());
                ops.pop();
            }
            ops.push(op);
        }
        vector<string> toRpn(vector<string> tokens) {
            vector<string> ans;
            stack<string> ops;
            for (auto &s : tokens) {
                if (isdigit(s[0])) ans.push_back(s);
                else pushOps(ans, ops, s);
            }
            pushOps(ans, ops);
            return ans;
        }
        int calc(vector<string> rpn) {
            stack<int> s;
            int n;
            for (auto &t : rpn) {
                if (isdigit(t[0])) s.push(stoi(t));
                else {
                    n = s.top();
                    s.pop();
                    switch (t[0]) {
                        case '+': s.top() += n; break;
                        case '-': s.top() -= n; break;
                        case '*': s.top() *= n; break;
                        case '/': s.top() /= n; break;
                    }
                }
            }
            return s.top();
        }
    public:
        int calculate(string s) {
            return calc(toRpn(tokenize(s)));
        }
    };
    
  • from collections import deque
    
    
    class Solution(object):
      def calculate(self, s):
        """
        :type s: str
        :rtype: int
        """
        i = 0
        queue = deque([])
        while i < len(s):
          if s[i] == " ":
            i += 1
          elif s[i] in "-+*/":
            queue.append(s[i])
            i += 1
          else:
            start = i
            while i < len(s) and s[i] not in "+-*/ ":
              i += 1
            num = int(s[start:i])
            queue.append(num)
            while len(queue) > 2 and queue[-2] in "*/":
              b = queue.pop()
              ops = queue.pop()
              a = queue.pop()
              if ops == "*":
                queue.append(a * b)
              elif ops == "/":
                queue.append(int(float(a) / b))
              else:
                return "invalid"
        if queue:
          a = queue.popleft()
          while len(queue) >= 2:
            ops = queue.popleft()
            b = queue.popleft()
            if ops == "+":
              a = a + b
            elif ops == "-":
              a = a - b
          return a
        return 0
    
    

All Problems

All Solutions