Example:
Input: ["6", "3", "-", "3", "/"] Output: 1 Explanation: ((6 - 3) / 3) = 1
Approach: Use stack. Whenever an operator comes, pop 2 values from stack and apply the operation and push the result back to stack. Please note that for "-" operator a single operand will also be enough.
public static int EvalRPN(string[] tokens)
{
Stack<int> stack = new Stack<int>();
foreach(string token in tokens)
{
if (IsOperator(token))
{
if (stack.Count >= 2)
{
int operand2 = stack.Pop();
int operand1 = stack.Pop();
int operationResult = ExecuteOperation(token, operand1, operand2);
stack.Push(operationResult);
}
else if (stack.Count == 1 && token == "-") // special handling of "-"
{
int num = stack.Pop();
stack.Push(-num);
}
}
else
{
stack.Push(int.Parse(token));
}
}
return stack.Pop();
}
private static int ExecuteOperation(string operatorStr, int operand1, int operand2)
{
switch (operatorStr)
{
case "+": return operand1 + operand2;
case "-": return operand1 - operand2;
case "*": return operand1 * operand2;
default: return operand1 / operand2;
}
}
private static bool IsOperator(string str)
{
return str == "+" || str == "-" || str == "*" || str == "/";
}
No comments:
Post a Comment