| LeetCode[227] Basic Calculator II
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.
You may assume that the given expression is always valid.
Some examples: - "3+2*2" = 7
- " 3/2 " = 1
- " 3+5 / 2 " = 5
复杂度
O(N), O(N)
思路
用两个stack来分别记录当前的结果和操作符(operator), 注意每一次统计当前的operand的时候，要看一下下一位的操作符。如果下一位是high operator('+'或'/'), 就要先把当前的数和操作符都要先push回stack保留数据，如果当前stack不为空且已经有高位运算符在stack的顶部，就先计算一次重新计算当前的数字，再考虑之后的运算。
有一种replace all multiple spaces with one space的方法，是s.replaceAll("\s+",""), s 表示的是匹配任意的空白符，包括空格，制表符(Tab)，换行符，中文全角空格等。也可以用更简单的方法，replaceAll(" +", "")。
代码 - public double calculator(String s) {
- // delete multiple spaces
- s = s.trim().replaceAll(" +", "");
- char[] arr = s.toCharArray();
- Stack<Double> res = new Stack<>();
- Stack<Character> operator = new Stack<>();
- res.push(0.0);
- operator.push('+');
- for(int i = 0; i < arr.length; i ++) {
- double val = 0;
- int j = i;
- while(j < arr.length && Character.isDigit(arr[j])) {
- val *= 10;
- val += arr[j] - '0';
- j ++;
- }
- //
- if(!operator.isEmpty() && isHighOp(operator.peek())) {
- double temp = getValue(res.pop(), val,operator.pop());
- val = temp;
- }
- if(j < arr.length && isHighOp(arr[j])) {
- res.push(val);
- operator.push(arr[j]);
- }
- else {
- double temp = getValue(res.pop(), val, operator.pop());
- res.push(temp);
- if(j < arr.length) operator.push(arr[j]);
- }
- i = j;
- }
- // notice the format;
- DecimalFormal df = new DecimalFormat("#.##");
- return Double.parseDouble(df.format(res.pop()));
- }
- public boolean isHighOp(Character ch) {
- return ch == '*' || ch == '/';
- }
- public double getValue(double op1, double op2, Character ch) {
- if(ch == '+') return op1 + op2;
- if(ch == '-') return op1 - op2;
- if(ch == '*') return op1 * op2;
- return op1 / op2;
- }
| 
