Welcome to Subscribe On Youtube
Question
Formatted question description: https://leetcode.ca/all/224.html
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 .
Example 1:
Input: "1 + 1"
Output: 2
Example 2:
Input: " 2-1 + 2 "
Output: 3
Example 3:
Input: "(1+(4+5+2)-3)+(6+8)"
Output: 23
Note:
You may assume that the given expression is always valid.
Do not use the eval built-in library function.
Algorithm
The title restricts the expressions with only plus and minus
signs, numbers, parentheses and spaces, and there is no multiplication and division, so there is no priority of calculation.
A stack
is needed to assist the calculation, and a variable sign is used to represent the current symbol.
We traverse the given string s
,
- If you encounter a number, because it may be a multi-digit number, we need to use a while loop to read all the subsequent numbers in, and then use
sign*num
to update the result res; - If a
plus sign
is encountered, sign is assigned to 1, and if aminus sign
is encountered, it is assigned to -1; - If a
left parenthesis
is encountered, push the current result res and sign onto the stack,reset
res to 0 and reset to 1; - If the
closing parenthesis
is encountered, the result res is multiplied by the symbol on the top of the stack, the top element of the stack is popped, and the result is res plus the number on the top of the stack, and the top element of the stack is popped.
Code
Java
-
import java.util.Stack; public class Basic_Calculator { class Solution { public int calculate(String s) { int res = 0; int num = 0; int sign = 1; int n = s.length(); Stack<Integer> sk = new Stack<>(); for (int i = 0; i < n; ++i) { char c = s.charAt(i); if (c >= '0') { num = 10 * num + (c - '0'); } else if (c == '+' || c == '-') { res += sign * num; // possible overflow, eg. -1 * Integer.MIN_VALUE num = 0; sign = (c == '+') ? 1 : -1; } else if (c == '(') { sk.push(res); // not c-'0' sk.push(sign); res = 0; sign = 1; num = 0; // this line can be removed, here for clarity, since it's set to 0 when hitting operator +/- } else if (c == ')') { res += sign * num; num = 0; res *= sk.peek(); sk.pop(); // sign @note: can be replaced by just `-1*val` res += sk.peek(); sk.pop(); // then previous result } } res += sign * num; // @note: final check, if no ')' to trigger stack pop stuff return res; } } }
-
// OJ: https://leetcode.com/problems/basic-calculator/ // Time: O(N) // Space: O(N) class Solution { 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; } vector<string> toRpn(vector<string> tokens) { vector<string> ans; stack<string> ops; for (auto &s : tokens) { switch (s[0]) { case '(': ops.push(s); break; case ')': while (ops.top() != "(") { ans.push_back(ops.top()); ops.pop(); } ops.pop(); break; case '+': case '-': if (ops.size() && (ops.top() == "+" || ops.top() == "-")) { ans.push_back(ops.top()); ops.pop(); } ops.push(s); break; default: ans.push_back(s); break; } } while (ops.size()) { ans.push_back(ops.top()); ops.pop(); } return ans; } int calc(vector<string> rpn) { stack<int> s; for (auto &t : rpn) { switch (t[0]) { case '+': case '-': { int b = s.top(); s.pop(); s.top() += t == "+" ? b : -b; break; } default: s.push(stoi(t)); break; } } return s.top(); } public: int calculate(string s) { return calc(toRpn(tokenize(s))); } };
-
class Solution: def calculate(self, s: str) -> int: ans = 0 num = 0 sign = 1 stack = [sign] # stack[-1]: current env's sign for c in s: if c.isdigit(): num = num * 10 + (ord(c) - ord('0')) elif c == '(': stack.append(sign) elif c == ')': stack.pop() elif c == '+' or c == '-': ans += sign * num sign = (1 if c == '+' else -1) * stack[-1] # after all + or -, the sign for current num num = 0 return ans + sign * num ############# class Solution(object): def calculate(self, s): """ :type s: str :rtype: int """ s = "(" + s + ")" stack = [] _stack = [] i = 0 while i < len(s): if s[i] == " ": i += 1 elif s[i] == "(": _stack.append(len(stack)) i += 1 elif s[i] == ")": start = _stack.pop() j = start a = stack[j] while j + 2 < len(stack): ops = stack[j + 1] if ops == "+": a = a + stack[j + 2] elif ops == "-": a = a - stack[j + 2] else: return "invalid" j += 2 k = len(stack) - start while k > 0: stack.pop() k -= 1 stack.append(a) i += 1 elif s[i] in "+-": stack.append(s[i]) i += 1 else: start = i while i < len(s) and s[i] not in "-+() ": i += 1 num = int(s[start:i]) stack.append(num) return stack[0]