题目

Implement a basic calculator to evaluate a simple expression string.

The expression string contains only non-negative integers, +, -, *, / operators and empty spaces ``. The integer division should truncate toward zero.

Example 1:

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

Example 2:

  1. Input: " 3/2 "
  2. Output: 1

Example 3:

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

Note:

  • You may assume that the given expression is always valid.
  • Do not use the eval built-in library function.

题意

计算只包含+, -, *, /和空格的数学表达式的值。

思路

方法一：从后向前遍历字符串，遇空格跳过，遇*, /压入操作符栈中，遇数字压入操作数栈中，遇’+’, ‘-‘需要进行判断：如果操作符栈栈顶为*或/，则从操作数栈和操作符栈分别出栈，将计算结果压回操作数栈，重复上述过程直到操作符栈为空或其栈顶为+, -，再将当前的+, -压入操作符栈中；其余情况则直接将+, -压入操作符栈中。全部遍历完后，重复出栈操作数栈和操作符栈计算结果即可。

方法二：从前向后遍历，参考自 [LeetCode] 227. Basic Calculator II 基本计算器之二。

代码实现

Java

从后向前遍历

  1. class Solution {
  2.     public int calculate(String s) {
  3.         Deque<Integer> nums = new ArrayDeque<>();
  4.         Deque<Character> ops = new ArrayDeque<>();
  6.         for (int i = s.length() - 1; i >= 0; i--) {
  7.             char c = s.charAt(i);
  8.             if (c == ' ') {
  9.                 continue;
  10.             } else if (c == '+' || c == '-') {
  11.                 while (!ops.isEmpty() && (ops.peek() == '*' || ops.peek() == '/')) {
  12.                     int a = nums.pop();
  13.                     int b = nums.pop();
  14.                     char op = ops.pop();
  15.                     int cal = op == '*' ? a * b : a / b;
  16.                     nums.push(cal);
  17.                 }
  18.                 ops.push(c);
  19.             } else if (c == '*' || c == '/') {
  20.                 ops.push(c);
  21.             } else {
  22.                 int num = c - '0';
  23.                 int zeros = 10;
  24.                 while (i - 1 >= 0 && s.charAt(i - 1) <= '9' && s.charAt(i - 1) >= '0') {
  25.                     num = (s.charAt(i - 1) - '0') * zeros + num;
  26.                     zeros *= 10;
  27.                     i--;
  28.                 }
  29.                 nums.push(num);
  30.             }
  31.         }
  33.         while (nums.size() != 1) {
  34.             int a = nums.pop();
  35.             int b = nums.pop();
  36.             char op = ops.pop();
  37.             int cal = (op == '+' ? a + b : op == '-' ? a - b : op == '*' ? a * b : a / b);
  38.             nums.push(cal);
  39.         }
  41.         return nums.pop();
  42.     }
  43. }

从前向后遍历

  1. class Solution {
  2.     public int calculate(String s) {
  3.         Deque<Integer> stack = new ArrayDeque<>();
  4.         int factor = 1;
  5.         for (int i = 0; i < s.length(); i++) {
  6.             char c = s.charAt(i);
  7.             if (c == ' ') {
  8.                 continue;
  9.             } else if (c == '*' || c == '/') {
  10.                 int a = stack.pop();
  11.                 int b = 0;
  12.                 while (!(s.charAt(i + 1) >= '0' && s.charAt(i + 1) <= '9')) {
  13.                     i++;
  14.                 }
  15.                 while (i + 1 < s.length() && s.charAt(i + 1) >= '0' && s.charAt(i + 1) <= '9') {
  16.                     b = b * 10 + s.charAt(i + 1) - '0';
  17.                     i++;
  18.                 }
  19.                 stack.push(c == '*' ? a * b : a / b);
  20.             } else if (c == '+' || c == '-') {
  21.                 factor = c == '+' ? 1 : -1;
  22.             } else {
  23.                 int num = c - '0';
  24.                 while (i + 1 < s.length() && s.charAt(i + 1) >= '0' && s.charAt(i + 1) <= '9') {
  25.                     num = num * 10 + s.charAt(i + 1) - '0';
  26.                     i++;
  27.                 }
  28.                 stack.push(num * factor);
  29.             }
  30.         }
  31.         while (stack.size() != 1) {
  32.             stack.push(stack.pop() + stack.pop());
  33.         }
  34.         return stack.pop();
  35.     }
  36. }

JavaScript

  1. /**
  2.  * @param {string} s
  3.  * @return {number}
  4.  */
  5. var calculate = function (s) {
  6.   let nums = []
  7.   let op = 1
  8.   let i = 0
  9.   let reg = /[0-9]/
  11.   while (i < s.length) {
  12.     if (reg.test(s[i])) {
  13.       let num = parseInt(s[i])
  14.       while (++i < s.length && reg.test(s[i])) {
  15.         num = num * 10 + parseInt(s[i])
  16.       }
  17.       nums.push(op * num)
  18.     } else if (s[i] === '+' || s[i] === '-') {
  19.       op = s[i++] === '+' ? 1 : -1
  20.     } else if (s[i] === '*' || s[i] === '/') {
  21.       let c = s[i]
  22.       let A = nums.pop()
  23.       while (s[++i] === ' ') {}
  24.       let B = parseInt(s[i])
  25.       while (++i < s.length && reg.test(s[i])) {
  26.         B = B * 10 + parseInt(s[i])
  27.       }
  28.       nums.push(c === '*' ? A * B : Math.trunc(A / B))
  29.     } else {
  30.       i++
  31.     }
  32.   }
  34.   return nums.reduce((acc, cur) => acc + cur)
  35. }