Baozi Training Leetcode solution 772: Basic Calculator III

包子面试培训

发布于 2019-08-27 14:53:15

59700

代码可运行

文章被收录于专栏：包子铺里聊IT包子铺里聊IT

运行总次数：0

代码可运行

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"

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

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2019-08-24，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

本文分享自包子铺里聊IT 微信公众号，前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

编程算法

登录后参与评论

0 条评论

热度