Skip to content

Latest commit

 

History

History

EvaluateReversePolishNotation

Folders and files

NameName
Last commit message
Last commit date

parent directory

..
 
 
 
 

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

Solution

使用栈保存数字:

  • 当遇到新的数字时,压入栈
  • 当遇到操作符时,从栈中弹出两个数,先后弹出的数分别为第二操作数、第一操作数.
  • 计算两个操作数和对应运算符进行运算的值,压入栈

Code

public int evalRPN(List<String> tokens) {
	LinkedList<String> repo = new LinkedList<String>();
	for (String token : tokens) {
		if (isOperator(token)) {
			String num1 = repo.pop();
			String num2 = repo.pop();
			int result = expr(num2, num1, token);
			repo.push(String.valueOf(result));
		} else {
			repo.push(token);
		}
	}
	return Integer.parseInt(repo.pop());
}