| Leetcode[224] Basic Calculator
Implement a basic calculator to evaluate a simple expression string.
The expression string may contain open ( and closing parentheses ),
the plus +, minus sign - or * or /, non-negative integers and empty spaces .
You may assume that the given expression is always valid.
Some examples: - "1 + 1" = 2
- " 2-1 + 2 " = 3
- "(1+(4+5+2)-3)+(6+8)" = 23
- "1 + (2 - 3 * 4)" = -9;
复杂度
O(N), O(N)
思路
将字符串先转换成后缀表达式，再将其evaluate出来。
前后缀表达式的转换：
http://scriptasylum.com/tutor...
后缀表达式的evaluation:
http://scriptasylum.com/tutor...
代码 - public int basicCalculator(String s) {
- s = s.trim().replaceAll(" +", "");
- Stack<Character> stack = new Stack<>();
- StringBuilder builder = new StringBuilder();
- char[] arr = s.toCharArray();
- for(int i = 0; i < arr.length; i ++) {
- if(arr[i] == '(') {
- stack.push('(');
- }
- else if(arr[i] == ')') {
- while(!stack.isEmpty() && stack.peek() != '(') {
- builder.append(stack.pop());
- }
- // pop out the '('
- stack.pop();
- }
- else if(Character.isDigit(arr[i])) {
- int val = 0;
- for(int j = i; j < arr.length && Character.isDigit(arr[j]); j ++) {
- val *= 10;
- val += arr[j] - '0';
- }
- builder.append(val);
- i = j - 1;
- }
- else {
- while(!stack.isEmpty() && rank(stack.peek()) >= rank(arr[j])) {
- builder.append(stack.pop());
- }
- stack.push(arr[j]);
- }
- }
- while(!stack.isEmpty()) {
- builder.append(stack.pop());
- }
- return evaluate(builder.toString());
- }
- public int rank(Character ch) {
- if(ch == '+' || ch == '-') return 1;
- else if(ch == '*' || ch == '/') return 2;
- // '('
- return 0;
- }
- public int evaluate(String s) {
- char[] arr = s.toCharArray();
- Stack<Integer> stack = new Stack<>();
- for(int i = 0; i < arr.length; i ++) {
- if(Character.isDigit(arr[i])) {
- stack.push(arr[i] - '0');
- }
- else {
- int op2 = stack.pop();
- int op1 = stack.pop();
- if(arr[i] == '+') {
- stack.push(op1 + op2);
- }
- else if(arr[i] == '-') {
- stack.push(op1 - op2);
- }
- else if(arr[i] == '*') {
- stack.push(op1 * op2);
- }
- else {
- stack.push(op1 / op2);
- }
- }
- }
- return stack.pop();
- }
| 
