Welcome to Subscribe On Youtube
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, and open '(' and closing parentheses ')'. 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 [-231, 231 - 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 = "1+1" Output: 2
Example 2:
Input: s = "6-4/2" Output: 4
Example 3:
Input: s = "2*(5+5*2)/3+(6/2+8)" Output: 21
Constraints:
1 <= s <= 104sconsists of digits,'+','-','*','/','(', and')'.sis a valid expression.
Solution
Three steps to evaluate a simple expression string:
Step 1:
Reformat the expression string by removing all empty spaces. If a minus sign ‘-‘ appears at the beginning of the expression string or immediately after an open parenthesis ‘(‘, add a zero ‘0’ before the minus sign.
Step 2:
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 digit, generate the number by considering one or more consecutive digits. If the element is an operator, separate it from the expression. Take into account the precedence of the current operator and the operator at the top of the stack. Note that ‘*’ and ‘/’ have higher precedence than ‘+’ and ‘-‘.
- If the precedence of the current operator is equal to or lower than the precedence of the operator at the top of the stack, pop operators from the stack and append them to the postfix expression in the same order they are popped, until either the stack is empty or the top operator has lower precedence than the current operator. Push the current operator onto the stack.
- If the current element is an open parenthesis, push it onto the stack. If it is a close parenthesis, pop operators from the stack and append them to the postfix expression in the same order they are popped, until the top of the stack is an open parenthesis. Finally, pop the open parenthesis from the stack.
- If the stack is not empty, pop the remaining operators from the stack and append them to the postfix expression in the same order they are popped.
Step 3:
Evaluate the postfix expression using a stack to store numbers. Loop over the postfix expression from start to end. If the current element is a number, push it onto the stack. If it is an operator, pop two numbers from the stack, perform the corresponding operation, and push the result back onto the stack. After iterating through the entire postfix expression, there should be only one number remaining in the stack, which represents 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(); } }; -
# good one, based on solution of Basic Calculator II class Solution: # dfs recursion def calculate(self, s: str) -> int: stack = [] num = 0 op = "+" i = 0 while i < len(s): c = s[i] if c.isdigit(): num = num * 10 + int(c) elif c == "(": j = self.findClosing(s, i) num = self.calculate(s[i+1:j]) # j is ')' i = j # out if, i will +1 below if c in "+-*/" or i == len(s) - 1: if op == "+": stack.append(num) elif op == "-": stack.append(-num) elif op == "*": stack[-1] *= num else: stack[-1] = int(stack[-1] / num) op = c num = 0 i += 1 return sum(stack) def findClosing(self, s: str, i: int) -> int: level = 0 while i < len(s): if s[i] == "(": level += 1 elif s[i] == ")": level -= 1 if level == 0: return i i += 1 return i ############## class Solution: # iterative def calculate(self, s: str) -> int: def evaluate_expression(stack): res = stack.pop() if stack else 0 # Evaluate the expression till we get '(' or empty stack while stack and stack[-1] != '(': sign = stack.pop() if sign == '+': res += stack.pop() elif sign == '-': res -= stack.pop() elif sign == '*': res *= stack.pop() elif sign == '/': res //= stack.pop() return res stack = [] # mix of num and operator n = len(s) i = 0 while i < n: if s[i].isdigit(): # Get the complete number and push it to the stack j = i while j < n and s[j].isdigit(): j += 1 stack.append(int(s[i:j])) i = j - 1 elif s[i] in '+-*/(': stack.append(s[i]) elif s[i] == ')': # Evaluate the expression within the parentheses res = evaluate_expression(stack) stack.pop() # Remove the opening '(' stack.append(res) i += 1 return evaluate_expression(stack) ############### class Solution: def calculate(self, s: str) -> int: if not s: return 0 # remove leading and trailing spaces and white spaces. s = s.strip().replace(" ", "") if not s: return 0 op_stack = [] num_stack = [] i = 0 while i < len(s): if s[i].isdigit(): num = 0 while i < len(s) and s[i].isdigit(): num = num * 10 + int(s[i]) i += 1 num_stack.append(num) else: op = s[i] if not op_stack: op_stack.append(op) i += 1 elif op == '+' or op == '-': top = op_stack[-1] if top == '(': op_stack.append(op) i += 1 else: self.calculate_helper(num_stack, op_stack) elif op == '*' or op == '/': top = op_stack[-1] if top == '(' or top == '+' or top == '-': op_stack.append(op) i += 1 else: self.calculate_helper(num_stack, op_stack) elif op == '(': op_stack.append(op) i += 1 elif op == ')': while op_stack[-1] != '(': self.calculate_helper(num_stack, op_stack) op_stack.pop() i += 1 while op_stack: self.calculate_helper(num_stack, op_stack) return num_stack[-1] def calculate_helper(self, num_stack, op_stack): num2 = num_stack.pop() num1 = num_stack.pop() op = op_stack.pop() if op == '+': ans = num1 + num2 elif op == '-': ans = num1 - num2 elif op == '*': ans = num1 * num2 else: ans = int(num1 / num2) num_stack.append(ans)