Alibi

My Life is Getting Better

Leetcode[224, 227] Basic Calculator

28 Nov 2015

###Task1 Implement a basic calculator to evaluate a simple expression string.

The expression string may contain open ( and closing parentheses ), the plus + or minus sign -, 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 Note: Do not use the eval built-in library function.

###Python

class Solution(object):
    def calculate(self, s):
        """
        :type s: str
        :rtype: int
        """
        self.calculator = ['+', '-', '*', '/']
        tokens = self.convertRPN(s)
        return self.compute(tokens)
    
    def convertRPN(self, s):
        stack = []
        tokens = []
        number = ''
        for c in s:
            if c.isdigit():
                number += c
            else:
                if number:
                    tokens.append(number)
                    number = ''
                if c == '(':
                    stack.append(c)
                elif c == ')':
                    while len(stack) and stack[-1] != '(':
                        tokens.append(stack.pop())
                    stack.pop()
                elif c in self.calculator:
                    while len(stack) and self.priority(stack[-1]) >= self.priority(c):
                        tokens.append(stack.pop())
                    stack.append(c)
        if number:
            tokens.append(number)
        while len(stack):
            tokens.append(stack.pop())
        return tokens
    
    def priority(self, c):
        map = { '+' : 1,
                '-' : 1,
                '*' : 2,
                '/' : 2
              }
        return map.get(c, 0)
    
    def compute(self, tokens):
        stack = []
        for token in tokens:
            if token not in self.calculator:
                stack.append(int(token))
            else:
                x = stack.pop()
                y = stack.pop()
                stack.append(self.computeRPN(token, x, y))
        return stack[0]
    
    def computeRPN(self, token, x, y):
        map = { '+': lambda x, y: y + x,
                '-': lambda x, y: y - x,
                '*': lambda x, y: y * x,
                '/': lambda x, y: y * 1.0 / x
              }
        return map[token](x, y)

###Java

public class Solution {
    public int calculate(String s) {
        String[] tokens = toRPN(s).split("\\s+");
        String op = "+-";
        Stack<String> stack = new Stack<String>();
        for (int i = 0; i < tokens.length; i++) {
            if (!op.contains(tokens[i])) {
                stack.push(tokens[i]);
            } else {
                int a = Integer.parseInt(stack.pop());
                int b = Integer.parseInt(stack.pop());
                switch (tokens[i]) {
                    case "+":
                        stack.push(String.valueOf(a + b));
                        break;
                    case "-":
                        stack.push(String.valueOf(b - a));
                        break;
                    default:
                        break;
                }
            }
        }
        
        return Integer.parseInt(stack.pop());
    }
    
    public String toRPN(String s) {
        char[] arr = s.toCharArray();
        Stack<Character> stack = new Stack<Character>();
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < arr.length; i++) {
            switch (arr[i]) {
                case '+':
                case '-':
                    while (!stack.isEmpty() && stack.peek() != '(') {
                        sb.append(" ");
                        sb.append(stack.pop());
                    }
                    sb.append(" ");
                    stack.push(arr[i]);
                    break;
                case '(':
                    stack.push(arr[i]);
                    break;
                case ')':
                    while (!stack.isEmpty() && stack.peek() != '(') {
                        sb.append(" ");
                        sb.append(stack.pop());
                    }
                    stack.pop();
                    break;
                case ' ':
                    break;
                default :
                    sb.append(arr[i]);
                    break;
            }
        }
        
        while (!stack.isEmpty()) {
            sb.append(" ");
            sb.append(stack.pop());
        }
        
        return sb.toString();
    }
}

###Points

表达式求值可以分解为下列两步完成：

1. 中缀表达式转为后缀表达式（逆波兰表达式）

2. 后缀表达式求值

以下内容来自百度百科：“后缀表达式”词条

中缀表达式转为后缀表达式的要点：

开始扫描；

数字时，加入后缀表达式；

运算符：

a. 若为 '('，入栈；

b. 若为 ')'，则依次把栈中的的运算符加入后缀表达式中，直到出现'('，从栈中删除'(' ；

c. 若为 除括号外的其他运算符， 当其优先级高于除'('以外的栈顶运算符时，直接入栈。否则从栈顶开始，依次弹出比当前处理的运算符优先级高和优先级相等的运算符，直到一个比它优先级低的或者遇到了一个左括号为止。
·当扫描的中缀表达式结束时，栈中的的所有运算符出栈；

后缀表达式求值的过程简述：

建立一个栈S

从左到右读表达式，如果读到操作数就将它压入栈S中

如果读到n元运算符(即需要参数个数为n的运算符)则取出由栈顶向下的n项按操作符运算，再将运算的结果代替原栈顶的n项，压入栈S中

如果后缀表达式未读完，则重复上面过程，最后输出栈顶的数值则为结束。

###Task2 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 Note: Do not use the eval built-in library function.

###python

Same code still works fine

Related Posts