using System;
using System.Collections.Generic;
using System.Text;

namespace ExpressionEvaluator {

  public class ExpressionParser {

    internal interface IParseResult {
      bool Succeeded { get; }
      bool Failed { get; }
      string RpnExpression { get; }
    }

    internal class SuccessfulParse : IParseResult {
      private string rpnExpression;
      public SuccessfulParse(string rpnExpression) {
        this.rpnExpression = rpnExpression;
      }
      public bool Succeeded {
        get { return true; }
      }
      public bool Failed {
        get { return !Succeeded; }
      }
      public string RpnExpression {
        get { return rpnExpression; }
      }
    }

    internal class FailedParse : IParseResult {
      public bool Succeeded {
        get { return false; }
      }

      public bool Failed {
        get { return !Succeeded; }
      }

      public string RpnExpression {
        get { return null; }
      }
    }

    internal class ParserState {
      private string expression;
      private int position;
      private char current;
      public char Current {
        get { return current; }
      }
      public void Advance() {
        position++;
        if (position >= expression.Length)
          current = '\0';
        else
          current = expression[position];
      }
      public ParserState(string expression) {
        this.expression = expression;
        position = -1;
        Advance();
      }
    }

    public static string ParseExpression(string expression) {
      ParserState state = new ParserState(expression);
      IParseResult result = ParseExpression(state);
      return result.RpnExpression;
    }

    private delegate IParseResult ParseDelegate(ParserState state);

    private static IParseResult ParseBinaryExpression(ParserState state,
                                                      ParseDelegate parseOperand,
                                                      ParseDelegate parseOperator) {
      IParseResult operandParse = parseOperand(state);
      if (operandParse.Failed)
        return operandParse;
      string rpn = operandParse.RpnExpression;

      IParseResult operatorParse = parseOperator(state);
      while (operatorParse.Succeeded) {
        operandParse = parseOperand(state);
        if (operandParse.Failed)
          return operandParse;
        rpn += operandParse.RpnExpression + operatorParse.RpnExpression;
        operatorParse = parseOperator(state);
      }
      return new SuccessfulParse(rpn);
    }

    private static IParseResult ParseExpression(ParserState state) {
      return ParseBinaryExpression(state, ParseTerm, ParseAdd);
    }

    private static IParseResult ParseTerm(ParserState state) {
      return ParseBinaryExpression(state, ParseFactor, ParseMultiply);
    }

    private static IParseResult ParseFactor(ParserState state) {
      IParseResult result = ParseNumber(state);
      if (result.Failed) {
        result = ParseParenthesizedExpression(state);
      }
      return result;
    }

    private static IParseResult ParseParenthesizedExpression(ParserState state) {
      if (state.Current != '(')
        return new FailedParse();
      state.Advance();

      IParseResult result = ParseExpression(state);
      if (result.Failed)
        return result;

      if (state.Current != ')')
        return new FailedParse();
      state.Advance();

      return result;
    }

    private static IParseResult ParseNumber(ParserState state) {
      char current = state.Current;
      if (char.IsDigit(current)) {
        state.Advance();
        return new SuccessfulParse(current.ToString());
      }
      return new FailedParse();
    }

    private static IParseResult ParseAdd(ParserState state) {
      char current = state.Current;
      switch (current) {
        case '+':
        case '-':
          state.Advance();
          return new SuccessfulParse(current.ToString());
        default:
          return new FailedParse();
      }
    }

    private static IParseResult ParseMultiply(ParserState state) {
      char current = state.Current;
      switch (current) {
        case '*':
        case '/':
          state.Advance();
          return new SuccessfulParse(current.ToString());
        default:
          return new FailedParse();
      }
    }
  }

  class RpnEvaluator {
    private static double Convert(char token) {
      return (int)token - (int)'0';
    }

    private static double Evaluate(char op, double rhs, double lhs) {
      switch (op) {
        case '+':
          return lhs + rhs;
        case '-':
          return lhs - rhs;
        case '*':
          return lhs * rhs;
        case '/':
          return lhs / rhs;
        default:
          throw new ArgumentException("unknown arithmetic operator", "op");
      }
    }

    public static double Evaluate(string rpn) {
      Stack<double> stack = new Stack<double>();
      foreach (char token in rpn) {
        if (char.IsDigit(token))
          stack.Push(Convert(token));
        else
          stack.Push(Evaluate(token, stack.Pop(), stack.Pop()));
      }
      return stack.Pop();
    }
  }

  class Program {
    static void Evaluate(string expr) {
      string rpn = ExpressionParser.ParseExpression(expr);
      Console.WriteLine(String.Format("{0} => {1} = {2}", expr, rpn, RpnEvaluator.Evaluate(rpn)));
    }

    static void Main(string[] args) {
      Evaluate("(1+2)*3");
      Evaluate("1+2*3");
      Evaluate("1+2/3");
      Evaluate("1/2-3");
      Evaluate("1+2*3-4");
      Evaluate("(1+2)*(3-4)");
      Evaluate("((1+2)*(3-4))-5");
      Evaluate("1+2+3+4");
      Evaluate("1*2*3*4");

      Console.ReadLine();
    }
  }
}