식은 숫자와 사칙연산 부호로 구성되어 있다. 먼저 Infix 방식으로 된 식을 PostFix 방식으로 변경하는데, 이는 부호의 우선순위에 따라 식을 변형하기 위한 것이다( O(n) ). PostFix로 변경된 식을 읽어 숫자인 경우는 스택에 집어 넣고, 연산자가 나타나면 스택에서 상위 2개의 값을 꺼내와서 해당 연산에 사용한다. 이 경우 먼저 꺼낸 것은 b에 나중에 꺼낸 것은 a에 두고 a-b와 같이 피연산자로 사용한다. 연산의 결과는 다시 스택에 넣고, 다음 식을 읽어 반복적으로 처리한다. 이렇게 모든 연산이 끝나면, 맨 마지막에는 스택에 결과값만 저장되므로 이를 꺼내서 리턴하면 된다.

public static void RunTest()
{
    string expr = "11 + 22 * 33 - 44";
    int result = Evaluate(expr);
    Console.WriteLine(result);
}

// 제약: 4칙연산만
static int Evaluate(string expression)
{                        
    // Convert to Postfix
    string postFix = ConvertToPostfix(expression);
    Console.WriteLine(postFix);

    // Evaluate Postfix
    return EvaluatePostfix(postFix);
}

static string ConvertToPostfix(string expr)
{            
    Stack<char> stack = new Stack<char>();
    StringBuilder sb = new StringBuilder();

    foreach (var ch in expr)
    {
        if (ch >= '0' && ch <= '9' || ch == ' ')
        {
            sb.Append(ch);
        }
        else if (ch == '*' || ch == '/')
        {                    
            stack.Push(ch);
        }
        else if (ch == '+' || ch == '-')
        {
            while (stack.Count > 0)
            {
                sb.Append(stack.Pop());
                sb.Append(' ');
            }
            stack.Push(ch);
        }
        else
        {
            throw new ArgumentException();
        }
    }

    if (stack.Count > 0)
    {
        sb.Append(stack.Pop());
    }

    return sb.ToString();
}

static int EvaluatePostfix(string expr)
{
    Stack<int> stack = new Stack<int>();
    int c = 0;

    for(int i=0; i<expr.Length; i++)
    {
        char ch = expr[i];

        if (ch == ' ') continue;
                
        if (ch >= '0' && ch <= '9')
        {
            string s = "";
            while (i<expr.Length && expr[i] >= '0' && expr[i] <= '9')
            {
                s += expr[i++];
            }
            i--;                    
            stack.Push(int.Parse(s));
        }
        else if (ch == '+' || ch == '-' || ch == '*' || ch == '/')
        {
            int b = stack.Pop();
            int a = stack.Pop();
            switch (ch)
            {
                case '+': c = a + b; break;
                case '-': c = a - b; break;
                case '*': c = a * b; break;
                case '/': c = a / b; break;
            }
            stack.Push(c);                    
        }
        else
        {
            throw new ArgumentException();
        }
    }

    return stack.Pop();
}