c# solution O(n) time, O(n) space using stack


  • 0
    M
    public class Solution {
          public int EvalRPN(string[] tokens)
            {
               if (tokens == null || tokens.Length == 0) return 0;          
                            
                Stack<string> stack = new Stack<string>();            
                HashSet<string> operators = new HashSet<string>() { "+", "-", "*", "/" };
                string peek = "*";
    
                for (int i = tokens.Length - 1; i >= 0; i--)
                {
                    string token = tokens[i];
                    if (stack.Count > 0) peek = stack.Peek();
                    stack.Push(token);
    
                    if (!operators.Contains(token))
                    {
                        while (!operators.Contains(peek))
                        {
                            int operand1 = int.Parse(stack.Pop());
                            int operand2 = int.Parse(stack.Pop());
                            string @operator = stack.Pop();
    
                            int tempResult = PerformOp(operand1, operand2, @operator);
                            if (stack.Count == 0) return tempResult;
                            peek = stack.Peek();
                            stack.Push(tempResult.ToString());
                        }
                    }
                }
                
                return int.Parse(stack.Pop());
            }
    
            private int PerformOp(int operand1, int operand2, string @operator)
            {
                switch (@operator)
                {
                    case "+": return operand1 + operand2;
                    case "-": return operand1 - operand2;
                    case "*": return operand1 * operand2;
                    case "/": return operand1 / operand2;
                    default: throw new ArgumentException(@operator);
                }
            }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.