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
Idea: Use stack. Scan the input string array from left to right. If the current position is a number, push it to the stack, otherwise pop two numbers and apply the operator and push the result back to the stack. The last element in the stack is the final result.
Time: O(n) Space: O(n)
Code:
public class Solution {
public int evalRPN(String[] tokens) {
Stack<Integer> stack=new Stack<Integer>();
for(int i=0;i<tokens.length;i++)
{
String s=tokens[i];
if(s.equals("+")||s.equals("-")||s.equals("*")||s.equals("/"))
{
int second=stack.pop();
int first=stack.pop();
int result=0;
if(s.equals("+"))
result=first+second;
if(s.equals("-"))
result=first-second;
if(s.equals("*"))
result=first*second;
if(s.equals("/"))
result=first/second;
stack.push(result);
}
else
stack.push(Integer.parseInt(s));
}
return stack.pop();
}
}
No comments:
Post a Comment