# Baozi Training Leetcode solution 772: Basic Calculator III

### 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 .

The expression string contains only non-negative integers, `+`, `-`, `*`, `/` operators , open `(` and closing parentheses `)` and empty spaces . 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 `[-2147483648, 2147483647]`.

Some examples:

```"1 + 1" = 2
" 6-4 / 2 " = 4
"2*(5+5*2)/3+(6/2+8)" = 21
"(2+6* 3+5- (3*14/7+2)*5)+3"=-12```

Note: Do not use the `eval` built-in library function.

### Video Tutorial

You can find the detailed video tutorial here

• B站

### Thought Process

This is an extension problem to Basic Calculator and Basic Calculator II. The differences are this time it really looks like a real calculator where it can do "+-*/" and with brackets.

It's still the same thought process with exactly the same idea before: having two stacks, one stack for the operator and the other for the operands, and with exactly the same calculating preferences before: calculate * and / before + and -. When seeing right bracket, continue popping till you see the left bracket.

This works fine assuming all the integers are non-negative, which they are supposed to be based on the problem description, and that's what most of the existing online leetcode solutions did as well.

As of 08/18/2019, this doesn't seem to be the case because leetcode decides to include "non-negative" integer test cases. See below case "-1+4*3/3/3"

Since we are practicing interviews, so let's also address the non-negative integer case as well

A few caveats

• (New) Handle negative integer starting case: "-1 + 2" or "-(2+3)*4"
• (New) Handle negative integer in between expression case: "1 - (-7)"
• (New) Calculate whenever you can calculate since division order matters 15 / 3 / 5 should be 1, but it won't work 3 / 5 = 0, then 15/0 invalid
• Pay attention to the order when popping out operands and calculate, the order matters.
• The number might not be just single digit, so need to read the char and convert the numbers

### Solutions

#### Two stacks for non-negative integer solution

Keep two stacks, operator and operands as explained in the above "Thought Process"

```  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
8         Stack<Long> operands = new Stack<>();
9         Stack<Character> operators = new Stack<>();
10         StringBuilder number = new StringBuilder(); // deal with non single digit numbers
11
12         while (i < s.length()) {
13             char c = s.charAt(i);
14
15             if (c == ' ') {
16                 i++;
17                 continue;
18             }
19
20             if (Character.isDigit(c)) {
21                 number.append(c);
22             } else if (this.isValidOperator(c)) {
23                 if (number.length() != 0) {
24                     operands.push(Long.parseLong(number.toString()));
25                     number = new StringBuilder();
26                 }
27
28                 // Basically based on different priority of operators
29                 if (operators.isEmpty()) {
30                     // it says it only contains non-negative integer, but now we have "-1 + 2", "-(2+3)*4"
31                     operators.push(c);
32                 } else if (!operators.isEmpty() && (c == '*' || c == '/') && (operators.peek() == '+' || operators.peek() == '-')) {
33                     // do nothing, keep pushing because */ has higher priority than +-
34                     operators.push(c);
35                 } else if (!operators.isEmpty() && (c == '+' || c == '-') && (operators.peek() == '*' || operators.peek() == '/')) {
36                     // calculate all previous expressions till hit the left bracket
37                     while (!operators.isEmpty() && operators.peek() != '(') {
38                         operands.push(this.calculateValue(operands, operators.pop()));
39                     }
40
41                     operators.push(c);
42                 } else if (c == '(') {
43                     operators.push(c);
44                 } else if (c == ')') {
45                     if (number.length() != 0) {
46                         operands.push(Long.parseLong(number.toString()));
47                         number = new StringBuilder();
48                     }
49
50                     while (!operators.isEmpty() && operators.peek() != '(') {
51                         char op = operators.pop();
52                         operands.push(this.calculateValue(operands, op));
53
54                     }
55                     operators.pop(); // pop out the left (
56
57                 } else {
58                     // for normal +- with previous +- || */ with previous */ case just calculate 1 step ahead
59                     // but because 15 / 3 / 5 should be 1, but it won't work 3 / 5 = 0, so we have to calculate
60                     // every time we can calculate and get result
61
62                     if (!operators.isEmpty() && operators.peek() != '(') {
63                         operands.push(this.calculateValue(operands, operators.pop()));
64                     }
65
66                     operators.push(c);
67
68
69                 }
70             }
71             i++;
72         }
73
74         if (number.length() != 0) {
75             operands.push(Long.parseLong(number.toString()));
76         }
77         // for "3+2*2" case that's why we need a while loop
78         while (!operators.isEmpty()) {
79             operands.push(this.calculateValue(operands, operators.pop()));
80         }
81
82         return (int)operands.pop().longValue();
83     }
84
85     private boolean isValidOperator(char op) {
86         if (op == '+' || op == '-' || op == '*' || op == '/' || op == '(' || op == ')') {
87             return true;
88         }
89         return false;
90     }
91
92     private long calculateValue(Stack<Long> operands, char op) {
93         long o2 = operands.pop();
94         long o1 = operands.pop();
95
96         if (op == '+') {
97             return o1 + o2;
98         } else if (op == '-') {
99             return o1 - o2;
100         } else if (op == '*') {
101             return o1 * o2;
102         } else if (op == '/') {
103             return o1 / o2;
104         } else {
105             throw new IllegalArgumentException("invalid op! " + op);
106         }
107     }```

Time Complexity: O(N), N is the length of the string

Space Complexity: O(N), extra stack is needed

#### Two stacks for negative integer solution

Essentially how do address the below two situations given the current code structure

• (New) Handle negative integer starting case. I simply just check if the first char in trimmed string is "-", and push a -1 into operands and "*" into operator. (e.g., -(a+b) = -1 * (a+b) and -a = -1 * a) "-1 + 2" or "-(2+3)*4"
• (New) Handle negative integer in between expression case. This is a bit hacky because a "-" in the middle of the expression could mean two things: a normal minus sign or a negative sigh denoting negative integer. Luckily "1 - - 2" would not be a valid case which means there should always be a left bracket before the negative sign for negative integer. What I did was using isNegativeNumberFollowingLeftBracket to find those cases and put a -1 and * into the operator and operands respectively "1 - (-7)"
```  1 public int calculate(String s) {
2         if (s == null || s.length() == 0) {
3             throw new IllegalArgumentException("invalid input");
4         }
5
6         s = s.trim();
7         int i = 0;
8
9         Stack<Long> operands = new Stack<>();
10         Stack<Character> operators = new Stack<>();
11         StringBuilder number = new StringBuilder(); // deal with non single digit numbers
12
13         while (i < s.length()) {
14             char c = s.charAt(i);
15
16             if (c == ' ') {
17                 i++;
18                 continue;
19             }
20
21             if (Character.isDigit(c)) {
22                 number.append(c);
23             } else if (this.isValidOperator(c)) {
24                 if (number.length() != 0) {
25                     operands.push(Long.parseLong(number.toString()));
26                     number = new StringBuilder();
27                 }
28
29                 // Basically based on different priority of operators
30                 if (operators.isEmpty()) {
31                     // it says it only contains non-negative integer, but now we have "-1 + 2", "-(2+3)*4"
32                     // this is to deal with the starting negative case
33                     if (c == '-' && i == 0) {
34                         operands.push(-1L);
35                         operators.push('*');
36                     } else {
37                         operators.push(c);
38                     }
39                 } else if (!operators.isEmpty() && (c == '*' || c == '/') && (operators.peek() == '+' || operators.peek() == '-')) {
40                     // do nothing, keep pushing because */ has higher priority than +-
41                     operators.push(c);
42                 } else if (!operators.isEmpty() && (c == '+' || c == '-') && (operators.peek() == '*' || operators.peek() == '/')) {
43                     // calculate all previous expressions till hit the left bracket
44                     while (!operators.isEmpty() && operators.peek() != '(') {
45                         operands.push(this.calculateValue(operands, operators.pop()));
46                     }
47
48                     operators.push(c);
49                 } else if (c == '(') {
50                     operators.push(c);
51                     // this is to deal with 1 * (-7+2) case
52                     if (this.isNegativeNumberFollowingLeftBracket(s, i + 1)) {
53                         operands.push(-1L);
54                         operators.push('*');
55                         while (i < s.length()) {
56                             if (s.charAt(i) == '-') {
57                                 // i++;  // skip this '-', later we i++ on line 129
58                                 break;
59                             }
60                             i++;
61                         }
62                     }
63                 } else if (c == ')') {
64                     if (number.length() != 0) {
65                         operands.push(Long.parseLong(number.toString()));
66                         number = new StringBuilder();
67                     }
68
69                     while (!operators.isEmpty() && operators.peek() != '(') {
70                         char op = operators.pop();
71                         operands.push(this.calculateValue(operands, op));
72
73                     }
74                     operators.pop(); // pop out the left (
75
76                 } else {
77                     // for normal +- with previous +- || */ with previous */ case just calculate 1 step ahead
78                     // but because 15 / 3 / 5 should be 1, but it won't work 3 / 5 = 0, so we have to calculate
79                     // every time we can calculate and get result
80                     if (!operators.isEmpty() && operators.peek() != '(') {
81                         operands.push(this.calculateValue(operands, operators.pop()));
82                     }
83                     operators.push(c);
84                 }
85             }
86             i++;
87         }
88
89         if (number.length() != 0) {
90             operands.push(Long.parseLong(number.toString()));
91         }
92         // for "3+2*2" case that's why we need a while loop
93         while (!operators.isEmpty()) {
94             operands.push(this.calculateValue(operands, operators.pop()));
95         }
96
97         return (int)operands.pop().longValue();
98     }
99
100     // given the current index(this would normally be the index after the '(', find out if there is
101     // a negative integer following the '('
102     private boolean isNegativeNumberFollowingLeftBracket(String s, int index) {
103         while (index < s.length()) {
104             char c = s.charAt(index);
105             if (c == ' ') {
106                 index++;
107                 continue;
108             }
109             if (c == '-') {
110                 return this.isDigitFollowing(s, index + 1);
111             } else {
112                 return false;
113             }
114         }
115         return false;
116     }
117
118     // given the current index, find out if it's a digit following it.
119     private boolean isDigitFollowing(String s, int index) {
120         while (index < s.length()) {
121             char c = s.charAt(index);
122             if (c == ' ') {
123                 index++;
124                 continue;
125             }
126             if (Character.isDigit(c)) {
127                 return true;
128             }
129             return false;
130         }
131         return false;
132     }
133
134
135     private boolean isValidOperator(char op) {
136         if (op == '+' || op == '-' || op == '*' || op == '/' || op == '(' || op == ')') {
137             return true;
138         }
139         return false;
140     }
141
142     private long calculateValue(Stack<Long> operands, char op) {
143         long o2 = operands.pop();
144         long o1 = operands.pop();
145
146         if (op == '+') {
147             return o1 + o2;
148         } else if (op == '-') {
149             return o1 - o2;
150         } else if (op == '*') {
151             return o1 * o2;
152         } else if (op == '/') {
153             return o1 / o2;
154         } else {
155             throw new IllegalArgumentException("invalid op! " + op);
156         }
157     }```

Time Complexity: O(N), N is the length of the string

Space Complexity: O(N), extra stack is needed

0 条评论