Question

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

Given a string s which represents an expression, evaluate this expression and return its value.

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 [-2³¹, 2³¹ - 1].

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

Example 1:

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

Example 2:

Input: s = " 3/2 "
Output: 1

Example 3:

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

Constraints:

1 <= s.length <= 3 * 10⁵
s consists of integers and operators ('+', '-', '*', '/') separated by some number of spaces.
s represents a valid expression.
All the integers in the expression are non-negative integers in the range [0, 2³¹ - 1].
The answer is guaranteed to fit in a 32-bit integer.

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

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;
        }
    }
}

############

class Solution {
    public int calculate(String s) {
        Deque<Integer> stk = new ArrayDeque<>();
        char sign = '+';
        int v = 0;
        for (int i = 0; i < s.length(); ++i) {
            char c = s.charAt(i);
            if (Character.isDigit(c)) {
                v = v * 10 + (c - '0');
            }
            if (i == s.length() - 1 || c == '+' || c == '-' || c == '*' || c == '/') {
                if (sign == '+') {
                    stk.push(v);
                } else if (sign == '-') {
                    stk.push(-v);
                } else if (sign == '*') {
                    stk.push(stk.pop() * v);
                } else {
                    stk.push(stk.pop() / v);
                }
                sign = c;
                v = 0;
            }
        }
        int ans = 0;
        while (!stk.isEmpty()) {
            ans += stk.pop();
        }
        return ans;
    }
}

// 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)));
    }
};

class Solution:
    def calculate(self, s: str) -> int:
        v, n = 0, len(s)
        sign = '+'
        stk = []
        for i, c in enumerate(s):
            if c.isdigit():
                v = v * 10 + int(c)
            if i == n - 1 or c in '+-*/':
                if sign == '+':
                    stk.append(v)
                # for "10-2*5": when '-' encountered, var 'sign' is still +
                # so '10' will be pushed to stk before setting sign to -
                elif sign == '-':
                    stk.append(-v)
                elif sign == '*':
                    stk.append(stk.pop() * v)
                elif sign == '/':
                    stk.append(int(stk.pop() / v))
                else:
                    print("operator not supported")

                sign = c
                v = 0
        return sum(stk)
############

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

func calculate(s string) int {
	sign := '+'
	stk := []int{}
	v := 0
	for i, c := range s {
		digit := '0' <= c && c <= '9'
		if digit {
			v = v*10 + int(c-'0')
		}
		if i == len(s)-1 || !digit && c != ' ' {
			switch sign {
			case '+':
				stk = append(stk, v)
			case '-':
				stk = append(stk, -v)
			case '*':
				stk[len(stk)-1] *= v
			case '/':
				stk[len(stk)-1] /= v
			}
			sign = c
			v = 0
		}
	}
	ans := 0
	for _, v := range stk {
		ans += v
	}
	return ans
}

using System.Collections.Generic;
using System.Linq;

struct Element
{
    public char Op;
    public int Number;
    public Element(char op, int number)
    {
        Op = op;
        Number = number;
    }
}

public class Solution {
    public int Calculate(string s) {
        var stack = new Stack<Element>();
        var readingNumber = false;
        var number = 0;
        var op = '+';
        foreach (var ch in ((IEnumerable<char>)s).Concat(Enumerable.Repeat('+', 1)))
        {
            if (ch >= '0' && ch <= '9')
            {
                if (!readingNumber)
                {
                    readingNumber = true;
                    number = 0;
                }
                number = (number * 10) + (ch - '0');
            }
            else if (ch != ' ')
            {
                readingNumber = false;
                if (op == '+' || op == '-')
                {
                    if (stack.Count == 2)
                    {
                        var prev = stack.Pop();
                        var first = stack.Pop();
                        if (prev.Op == '+')
                        {
                            stack.Push(new Element(first.Op, first.Number + prev.Number));
                        }
                        else // '-'
                        {
                            stack.Push(new Element(first.Op, first.Number - prev.Number));
                        }
                    }
                    stack.Push(new Element(op, number));
                }
                else
                {
                    var prev = stack.Pop();
                    if (op == '*')
                    {
                        stack.Push(new Element(prev.Op, prev.Number * number));
                    }
                    else // '/'
                    {
                        stack.Push(new Element(prev.Op, prev.Number / number));
                    }
                }
                op = ch; 
            }
        }
        
        if (stack.Count == 2)
        {
            var second = stack.Pop();
            var first = stack.Pop();
            if (second.Op == '+')
            {
                stack.Push(new Element(first.Op, first.Number + second.Number));
            }
            else // '-'
            {
                stack.Push(new Element(first.Op, first.Number - second.Number));
            }
        }
        
        return stack.Peek().Number;
    }
}

227 - Basic Calculator II

Question

Algorithm

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

Code

All Problems

All Solutions