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

基本思路：

题目的意思是求逆波兰序列的值。自然而然的想到了利用栈来存放数字，辅以符号进行计算。

	public int evalRPN(String[] tokens)
	{
		int ret = 0;
		
		Stack<Integer> value = new Stack<Integer>();
		
		int index = 0;
		while(index<tokens.length)
		{
			//分两种情况，如果字符串长度为1，只有可能是运算符和不带符号的数字
			//如果长度大于1，那么肯定是带符号的数字
			if(tokens[index].length()==1)
			{
				char tmpch = tokens[index].charAt(0);
				if(tmpch>=‘0‘&&tmpch<=‘9‘)
				{
					value.push(tmpch-‘0‘);
				}
				else
				{
					if(value.size()<2)
					{
						return -1;
					}
					else
					{
						int one = value.pop();
						int two = value.pop();
						
						if(tmpch==‘+‘)
							ret = two+one;
						else if(tmpch==‘-‘)
							ret = two-one;
						else if(tmpch==‘*‘)
							ret = two*one;
						else
						{
							if(one==0)
								return -1;
							else
								ret = two/one;
						}
					}
					
					value.push(ret);
				}
				
			}
			else
				value.push(Integer.parseInt(tokens[index]));
			index++;
		}
		if(value.size()>1||value.size()<=0)
			return -1;
		return value.peek();
	}

Evaluate Reverse Polish Notation,布布扣,bubuko.com

Evaluate Reverse Polish Notation

原文：http://blog.csdn.net/cow__sky/article/details/21782345