Leetcode 227：基础计算器II，如何高效实现长尾词计算？

本文共计1232个文字，预计阅读时间需要5分钟。

问题描述：实现一个基本的计算器，用于评估一个简单的表达式字符串。该表达式字符串仅包含非负整数、+、-、*、/运算符和空格。整数除法应舍入到零。例如：实现一个基本的计算器，用于评估一个简单的表达式字符串。该表达式字符串仅包含非负整数、加、减、乘、除运算符和空格。整数除法应舍入到零。

Problem Statement

Implement a basic calculator to evaluate a simple expression string.

The expression string contains onlynon-negativeintegers,+,-,*,/operators and empty spaces. The integer division should truncate toward zero.

Example 1:

Input: "3+2*2" Output: 7

Example 2:

Input: " 3/2 " Output: 1

Example 3:

Input: " 3+5 / 2 " Output: 5

Note:

• You may assume that the given expression is always valid.
• Do notuse theevalbuilt-in library function.

Problem link

Video Tutorial

You can find the detailed video tutorial here

• Youtube
• B站

Thought Process

This problem is very similar to Basic Calculator. The difference is there is no parenthesis in this one, but there is * and / . We can use similar thought process by having two stacks, one stack for the operator and the other for the operands. We just need to pay attention the differentiate the operator‘s priority. For example, when you currently see a "+" or "-" and previous operator is "*" or "/", you need to pop up the operator stack and calculate. When you currently see a "*" or "/" and previous operator is "+" or "-", you should just keep pushing operator to stack. Else, they are at the same priority, we just do the normal calculation.

A few caveats

• Notice number overflow. "0- 2147483648". I don‘t think leetcode has this test case but it is a valid one. We should use Long.
• 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

Standard generic way

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 // even though leetcode does not have this use case System.out.println(ins.calculate("0-2147483648")); // -2147483648 8 // It can still pass with Integer, but use long for overflow case in general 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 if (c == ‘ ‘) { 16 i++; 17 continue; 18 } 19 20 if (Character.isDigit(c)) { 21 number.append(c); 22 } else if (c == ‘+‘ || c == ‘-‘ || c == ‘*‘ || c == ‘/‘) { 23 if (number.length() != 0) { 24 operands.push(Long.parseLong(number.toString())); 25 number = new StringBuilder(); 26 } 27 // Basically based on different priority of operators 28 if (operators.isEmpty()) { 29 operators.push(c); 30 } else if (!operators.isEmpty() && (c == ‘*‘ || c == ‘/‘) && (operators.peek() == ‘+‘ || operators.peek() == ‘-‘)) { 31 // do nothing, keep pushing because */ has higher priority than +- 32 operators.push(c); 33 } else if (!operators.isEmpty() && (c == ‘+‘ || c == ‘-‘) && (operators.peek() == ‘*‘ || operators.peek() == ‘/‘)) { 34 // calculate all previous expressions 35 while (!operators.isEmpty()) { 36 operands.push(this.calculateValue(operands, operators.pop())); 37 } 38 operators.push(c); 39 } else { 40 // only calculating one step, for */, and +- case, one step is fine 41 operands.push(this.calculateValue(operands, operators.pop())); 42 operators.push(c); 43 } 44 } 45 i++; 46 } 47 48 if (number.length() != 0) { 49 operands.push(Long.parseLong(number.toString())); 50 } 51 // for "3+2*2" case that‘s why we need a while loop 52 while (!operators.isEmpty()) { 53 operands.push(this.calculateValue(operands, operators.pop())); 54 } 55 56 return (int)operands.pop().longValue(); // Since it is Long, an object can‘t be cast to primitive, .longValue first then cast 57 } 58 59 60 private long calculateValue(Stack<Long> operands, char op) { 61 long o2 = operands.pop(); 62 long o1 = operands.pop(); 63 64 if (op == ‘+‘) { 65 return o1 + o2; 66 } else if (op == ‘-‘) { 67 return o1 - o2; 68 } else if (op == ‘*‘) { 69 return o1 * o2; 70 } else if (op == ‘/‘) { 71 return o1 / o2; 72 } else { 73 throw new IllegalArgumentException("invalid op!"); 74 } 75 }

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

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

Use one stack with two passes

Another neat and clean way to solve this problem is also similar to the "Use the sign method with one stack" in Basic Calculator. The idea is in the first pass, only calculate "*" and "/" and push the values into the stack, then have a 2nd pass to do the "+" and "-" calculations.

1 // Another thought is having 2 pass, first pass */, second pass +- 2 // "1 + 2 * 3 / 2" = 4, pretty clean 3 // "1 - 2 * 3 / 2" = -2 4 public int calculateTwoPass(String s) { 5 int len; 6 if (s == null || (len = s.length()) == 0) { 7 return 0; 8 } 9 Stack<Integer> stack = new Stack<Integer>(); 10 int num = 0; 11 // This is more like the previous sign 12 char sign = ‘+‘; 13 for (int i = 0; i < len; i++) { 14 if (Character.isDigit(s.charAt(i))) { 15 num = num * 10 + s.charAt(i) - ‘0‘; 16 } 17 18 if ((!Character.isDigit(s.charAt(i)) && ‘ ‘ != s.charAt(i)) || i == len - 1) { 19 if (sign == ‘-‘) { 20 stack.push(-num); 21 } 22 if (sign == ‘+‘) { 23 stack.push(num); 24 } 25 if (sign == ‘*‘) { 26 stack.push(stack.pop()*num); 27 } 28 if (sign == ‘/‘) { 29 stack.push(stack.pop()/num); 30 } 31 // reassign the current sign 32 sign = s.charAt(i); 33 num = 0; 34 } 35 } 36 37 int re = 0; 38 for (int i : stack){ 39 re += i; 40 } 41 return re; 42 }

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