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: 2

Example 2:

Input: " 2-1 + 2 "
Output: 3

Example 3:

Input: "(1+(4+5+2)-3)+(6+8)"
Output: 23

Note:

  • You may assume that the given expression is always valid.
  • 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

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

原文发布于微信公众号 - 包子铺里聊IT(baozitraining)

原文发表时间:2019-08-11

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

扫码关注云+社区

领取腾讯云代金券