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: 7Example 2:
Input: " 3/2 " Output: 1Example 3:
Input: " 3+5 / 2 " Output: 5
Note:
eval built-in library function.基本计算器II。题意跟版本一基本一样，多了乘法和除法的操作但是省去了括号，同时需要skip中间遇到的空格。思路依然是用stack，也是按字符遍历input，遇到乘号和除号的时候需要把栈顶元素pop出来，计算后把计算后的结果再放入栈内。记得当遍历到字符串最后的时候记得做最后一次结算，否则就会遗漏关于最后一个数字的相关运算。
时间O(n)
空间O(n)
Java实现
1 class Solution { 2 public int calculate(String s) { 3 // corner case 4 if (s == null || s.length() == 0) { 5 return 0; 6 } 7 8 // normal case 9 Stack<Integer> stack = new Stack<>(); 10 int res = 0; 11 char sign = ‘+‘; 12 int num = 0; 13 for (int i = 0; i < s.length(); i++) { 14 if (Character.isDigit(s.charAt(i))) { 15 num = s.charAt(i) - ‘0‘; 16 while (i + 1 < s.length() && Character.isDigit(s.charAt(i + 1))) { 17 num = num * 10 + s.charAt(i + 1) - ‘0‘; 18 i++; 19 } 20 } 21 if (!Character.isDigit(s.charAt(i)) && s.charAt(i) != ‘ ‘ || i == s.length() - 1) { 22 if (sign == ‘+‘) { 23 stack.push(num); 24 } 25 if (sign == ‘-‘) { 26 stack.push(-num); 27 } 28 if (sign == ‘*‘) { 29 stack.push(stack.pop() * num); 30 } 31 if (sign == ‘/‘) { 32 stack.push(stack.pop() / num); 33 } 34 sign = s.charAt(i); 35 num = 0; 36 } 37 } 38 39 for (int i : stack) { 40 res += i; 41 } 42 return res; 43 } 44 }
[LeetCode] 227. Basic Calculator II
原文：https://www.cnblogs.com/cnoodle/p/12903616.html