Baozi Training Leetcode Solution 224: Basic Calculator
Baozi Training Leetcode Solution 224: Basic Calculator
Blogger: https://blog.baozitraining.org/2019/08/leetcode-solution-224-basic-calculator.html
Youtube: https://youtu.be/pBHRDEOffbk
博客园: https://www.cnblogs.com/baozitraining/p/11326850.html
B站: https://www.bilibili.com/video/av62909935/
Problem Statement
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: 2Example 2:
Input: " 2-1 + 2 "
Output: 3Example 3:
Input: "(1+(4+5+2)-3)+(6+8)"
Output: 23Note:
- You may assume that the given expression is always valid.
- Do not use the
evalbuilt-in library function.
Problem link
Video Tutorial
You can find the detailed video tutorial here
- Youtube
- B站
Thought Process
A generic way for solving those calculating numbers problems is to use stack. More specifically, use two stacks: one stack for the operator and the other for the operands.
A few caveats
- Pay attention to the order when popping out operands and calculate, the order matters.
- The parenthesis matters, 2 - 1 + 2 = 3, while 2 - (1+2) = -1 = 2 - 1 - 2 if you want to remove the bracket you need to change the sign
- "1000" is a valid expression without any operators
- The number might not be just single digit, so need to read the char and convert the numbers
Solutions
Standard generic way
Keep two stacks, operator and operands. When we see left bracket, keep pushing to the stack. We calculate the values as normal within the inner most bracket. When we see right bracket, calculate and pop out the left bracket
1 public int calculate(String s) {
2 if (s == null || s.length() == 0) {
3 throw new IllegalArgumentException("Invalid input");
4 }
5
6 int i = 0;
7 Stack<Integer> operands = new Stack<>();
8 Stack<Character> operators = new Stack<>();
9 StringBuilder number = new StringBuilder();
10
11 while (i < s.length()) {
12 char c = s.charAt(i);
13 if (c == ' ') {
14 i++;
15 continue;
16 }
17
18 if (Character.isDigit(c)) {
19 number.append(c);
20 } else if (c == '(') {
21 operators.push(c);
22 } else if (c == ')') {
23 // push the current number to the operands stack
24 if (number.length() != 0) {
25 operands.push(Integer.parseInt(number.toString()));
26 number = new StringBuilder();
27 }
28
29 if (!operators.isEmpty() && operators.peek() != '(') {
30 char op = operators.pop();
31 operands.push(this.calculateValue(operands, op));
32 }
33 if (!operators.isEmpty()) { // pop the left bracket
34 operators.pop();
35 }
36 } else if (c == '+' || c == '-') {
37 if (number.length() != 0) {
38 operands.push(Integer.parseInt(number.toString()));
39 number = new StringBuilder();
40 }
41
42 if (!operators.isEmpty() && operators.peek() != '(') {
43 operands.push(this.calculateValue(operands, operators.pop()));
44 }
45
46 operators.push(c);
47 }
48 i++;
49 }
50
51
52 if (number.length() != 0) {
53 operands.push(Integer.parseInt(number.toString()));
54 }
55
56 // need this for the 1+1 case, don't need a while since we are only one step away
57 if (!operators.isEmpty()) {
58 operands.push(this.calculateValue(operands, operators.pop()));
59 }
60
61 return operands.pop();
62 }
63
64
65 private int calculateValue(Stack<Integer> operands, char operator) {
66 // Pay attention to the stack order
67 int o2 = operands.pop();
68 int o1 = operands.pop();
69
70 if (operator == '+') {
71 return o1 + o2;
72 } else if (operator == '-') {
73 return o1 - o2;
74 } else {
75 throw new IllegalArgumentException("invalid operator!");
76 }
77 }Time Complexity: O(N), N is the length of the string
Space Complexity: O(N), extra stack is needed
Use the sign method with one stack
The thought process is very similar to use the stacks, in this method, the clever part is it uses only one stack and also pushed a sign. +1 for "+" and -1 for "-1". Whenever there is a left bracket, you push the existing result and the sign into the stack. Whenever there is a right bracket, you pop up the sign and the value. Pretty neat!
1 // The main idea of this is the left bracket might change the sign of a number, however, this does not seem to be very generalized
2 // https://leetcode.com/problems/basic-calculator/discuss/62362/JAVA-Easy-Version-To-Understand!!!!!
3 public class Solution {
4 // 1-2-(4+5+2)-3
5 public int calculate(String s) {
6 int len = s.length(), sign = 1, result = 0;
7 // Use one stack for numbers, for operators used the sign, + -> 1, - -> -1
8 Stack<Integer> stack = new Stack<>();
9
10 for (int i = 0; i < len; i++) {
11 if (Character.isDigit(s.charAt(i))) {
12 int sum = s.charAt(i) - '0';
13 while (i + 1 < len && Character.isDigit(s.charAt(i + 1))) {
14 sum = sum * 10 + s.charAt(i + 1) - '0';
15 i++;
16 }
17 result += sum * sign;
18 } else if (s.charAt(i) == '+')
19 sign = 1;
20 else if (s.charAt(i) == '-')
21 sign = -1;
22 else if (s.charAt(i) == '(') {
23 stack.push(result);
24 stack.push(sign);
25 result = 0;
26 sign = 1;
27 } else if (s.charAt(i) == ')') {
28 // first pop is the sign, +1 or -1, second is the value
29 result = result * stack.pop() + stack.pop();
30 }
31
32 }
33 return result;
34 }
35 }Time Complexity: O(N), N is the length of the string
Space Complexity: O(N), extra stack is needed