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.

Problem link

 

Video Tutorial

You can find the detailed video tutorial here

• Youtube 
• 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"

 

An "non-negative" integer case

 

 

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

 

References

• Leetcode discussion on the clean solution (didn‘t work for non-negative integer case)