leetcode150.Evaluate Reverse Polish Notation

题目要求

Evaluate the value of an arithmetic expression in Reverse Polish Notation.

Valid operators are +, -, *, /. Each operand may be an integer or another expression.

Some examples:
  ["2", "1", "+", "3", "*"] -> ((2 + 1) * 3) -> 9
  ["4", "13", "5", "/", "+"] -> (4 + (13 / 5)) -> 6

计算后缀表达式。我们一般看到的数学表达式就是中缀表达式,也就是将符号放在两个数字之间。后缀表达式也就是将运算符放在相应数字的后面。后缀表达式相当于树中的后序遍历。

思路一:栈

当我们遇到数字时就将数字压入栈中,如果遇到操作符就将栈顶的两个数字弹出,并将其根据操作符计算结构并重新压入栈中。栈中剩下的最后的值就是我们的结果。

1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
18  
19  
20  
21  
22  
23  
24  
25  
public int (String[] tokens) {  
    LinkedList<Integer> stack = new LinkedList<Integer>();  
    for(String token : tokens){  
        if(token.equals("+")){  
            int operand1 = stack.pop();  
            int operand2 = stack.pop();  
            stack.push(operand2 + operand1);  
        }else if(token.equals("-")){  
            int operand1 = stack.pop();  
            int operand2 = stack.pop();  
            stack.push(operand2 - operand1);  
        }else if(token.equals("*")){  
            int operand1 = stack.pop();  
            int operand2 = stack.pop();  
            stack.push(operand2 * operand1);  
        }else if(token.equals("/")){  
            int operand1 = stack.pop();  
            int operand2 = stack.pop();  
            stack.push(operand2 / operand1);  
        }else{  
            stack.push(Integer.valueOf(token));  
        }  
    }  
    return stack.pop();  
}  

—|—

思路二:递归

从后缀表达式的末尾开始递归获取操作符对应的两个操作符。通过index获得对应位置的操作符。如果对应的还是操作符,则继续递归往前计算。

1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
18  
19  
20  
21  
22  
23  
24  
25  
26  
27  
28  
29  
int index;  
public int evalRPN2(String[] tokens){  
    index = tokens.length-1;  
    return recursive(tokens);  
}   
public int recursive(String[] tokens){  
    String current = tokens[index--];  
    int operand1, operand2;  
    switch(current){  
    case "+" :   
        operand1 = recursive(tokens);  
        operand2 = recursive(tokens);  
        return operand1 + operand2;  
    case "-" :  
        operand1 = recursive(tokens);  
        operand2 = recursive(tokens);  
        return operand2 - operand1;  
    case "*" :  
        operand1 = recursive(tokens);  
        operand2 = recursive(tokens);  
        return operand2 * operand1;  
    case "/" :  
        operand1 = recursive(tokens);  
        operand2 = recursive(tokens);  
        return operand2 / operand1;  
    default:  
        return Integer.valueOf(current);  
    }  
}  

—|—

糖果

糖果
LUA教程

Lapis框架的常用处理方法

Lapis框架的常用处理方法 Continue reading

MoonScript实现选择排序

Published on February 26, 2017

MoonScript与Redis客户端

Published on January 19, 2017