leetcode 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

维基百科例子

中缀表达式“5 + ((1 + 2) * 4) − 3”写作

5 1 2 + 4 * + 3 −

下表给出了该逆波兰表达式从左至右求值的过程,堆栈栏给出了中间值,用于跟踪算法。

输入 操作 堆栈 注释
5 入栈 5
1 入栈 5, 1
2 入栈 5, 1, 2
+ 加法运算 5, 3 (1, 2)出栈;将结果(3)入栈
4 入栈 5, 3, 4
* 乘法运算 5, 12 (3, 4)出栈;将结果(12)入栈
+ 加法运算 17 (5, 12)出栈;将结果 (17)入栈
3 入栈 17, 3
减法运算 14 (17, 3)出栈;将结果(14)入栈

计算完成时,栈内只有一个操作数,这就是表达式的结果:14

上述运算可以重写为如下运算链方法(用于HP的逆波兰计算器):[3]

1 2 + 4 * 5 + 3 −

 

逆波兰表达式代码:

public class ReversPoland {
    public int evalRPN(String[] tokens) {
    	Stack nums = new Stack<String>();
    	//Stack oper = new Stack<String>();
    	
    	for (int i = 0; i < tokens.length; ){
    		
    		if (isNumber(tokens[i])){
    			nums.push(tokens[i]);
    			i++;
    		}else{
    			int num1 = Integer.parseInt(nums.pop().toString());
    			int num2 = Integer.parseInt(nums.pop().toString());
    			nums.push(Excute(num2, tokens[i], num1));
    			i++;
    		}
    	}
        
        return Integer.parseInt(nums.peek().toString());
    }

        
        //计算两数字运算结果
	private int Excute(int num1, String string, int num2) {
		
		switch (string) {
		case "*":
			return num1*num2;
		case "/":
			return num1/num2;
		case "+":
		return num1 + num2;
		case "-":
			return num1 - num2;
		
		default:
			break;
		}
		return 0;
	}

	//判断是否是数字(包含整数负数)
       private boolean isNumber(String s) { 
		int i=0;
		if (s.charAt(0)== '-' && s.length() == 1)
			return false;
		
		if  (s.charAt(0) ==  '-' )
			i++;		
				
		for ( ;i <s.length(); i++){

			if (s.charAt(i) < '0' || s.charAt(i) >'9')
				return false;
			
		}
		return true;
		
	}
    
}



Tagged on: , ,

发表评论

电子邮件地址不会被公开。 必填项已用*标注

您可以使用这些HTML标签和属性: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>