Basic Calculator II (M)

題目

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:

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 not use the eval built-in library function.

題意

計算只包含+, -, *, /和空格的數學運算式的值，

思路

方法一：從后向前遍歷字串，遇空格跳過，遇*, /壓入運算子堆疊中，遇數字壓入運算元堆疊中，遇'+', '-'需要進行判斷：如果運算子堆疊堆疊頂為*或/，則從運算元堆疊和運算子堆疊分別出堆疊，將計算結果壓回運算元堆疊，重復上述程序直到運算子堆疊為慷訓其堆疊頂為+, -，再將當前的+, -壓入運算子堆疊中；其余情況則直接將+, -壓入運算子堆疊中，全部遍歷完后，重復出堆疊運算元堆疊和運算子堆疊計算結果即可，

方法二：從前向后遍歷，參考自 [LeetCode] 227. Basic Calculator II 基本計算器之二，

代碼實作

Java

從后向前遍歷

class Solution {
    public int calculate(String s) {
        Deque<Integer> nums = new ArrayDeque<>();
        Deque<Character> ops = new ArrayDeque<>();

        for (int i = s.length() - 1; i >= 0; i--) {
            char c = s.charAt(i);
            if (c == ' ') {
                continue;
            } else if (c == '+' || c == '-') {
                while (!ops.isEmpty() && (ops.peek() == '*' || ops.peek() == '/')) {
                    int a = nums.pop();
                    int b = nums.pop();
                    char op = ops.pop();
                    int cal = op == '*' ? a * b : a / b;
                    nums.push(cal);
                }
                ops.push(c);
            } else if (c == '*' || c == '/') {
                ops.push(c);
            } else {
                int num = c - '0';
                int zeros = 10;
                while (i - 1 >= 0 && s.charAt(i - 1) <= '9' && s.charAt(i - 1) >= '0') {
                    num = (s.charAt(i - 1) - '0') * zeros + num;
                    zeros *= 10;
                    i--;
                }
                nums.push(num);
            }
        }

        while (nums.size() != 1) {
            int a = nums.pop();
            int b = nums.pop();
            char op = ops.pop();
            int cal = (op == '+' ? a + b : op == '-' ? a - b : op == '*' ? a * b : a / b);
            nums.push(cal);
        }

        return nums.pop();
    }
}

從前向后遍歷

class Solution {
    public int calculate(String s) {
        Deque<Integer> stack = new ArrayDeque<>();
        int factor = 1;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == ' ') {
                continue;
            } else if (c == '*' || c == '/') {
                int a = stack.pop();
                int b = 0;
                while (!(s.charAt(i + 1) >= '0' && s.charAt(i + 1) <= '9')) {
                    i++;
                }
                while (i + 1 < s.length() && s.charAt(i + 1) >= '0' && s.charAt(i + 1) <= '9') {
                    b = b * 10 + s.charAt(i + 1) - '0';
                    i++;
                }
                stack.push(c == '*' ? a * b : a / b);
            } else if (c == '+' || c == '-') {
                factor = c == '+' ? 1 : -1;
            } else {
                int num = c - '0';
                while (i + 1 < s.length() && s.charAt(i + 1) >= '0' && s.charAt(i + 1) <= '9') {
                    num = num * 10 + s.charAt(i + 1) - '0';
                    i++;
                }
                stack.push(num * factor);
            }
        }
        while (stack.size() != 1) {
            stack.push(stack.pop() + stack.pop());
        }
        return stack.pop();
    }
}

JavaScript

/**
 * @param {string} s
 * @return {number}
 */
var calculate = function (s) {
  let nums = []
  let op = 1
  let i = 0
  let reg = /[0-9]/

  while (i < s.length) {
    if (reg.test(s[i])) {
      let num = parseInt(s[i])
      while (++i < s.length && reg.test(s[i])) {
        num = num * 10 + parseInt(s[i])
      }
      nums.push(op * num)
    } else if (s[i] === '+' || s[i] === '-') {
      op = s[i++] === '+' ? 1 : -1
    } else if (s[i] === '*' || s[i] === '/') {
      let c = s[i]
      let A = nums.pop()
      while (s[++i] === ' ') {}
      let B = parseInt(s[i])
      while (++i < s.length && reg.test(s[i])) {
        B = B * 10 + parseInt(s[i])
      }
      nums.push(c === '*' ? A * B : Math.trunc(A / B))
    } else {
      i++
    }
  }

  return nums.reduce((acc, cur) => acc + cur)
}

標籤：其他

上一篇：完全二叉樹的節點個數

下一篇：Unity周記: 2020.11.16-11.22