This program is an example of a simple interpreter. It evaluates an arithmetic expression provided as a string and displays a numerical result. For simplicity, the program assumes that the arithmetic expression is fully parenthesized.

The evaluation of arithmetic expressions is conducted with the Dijkstra's two-stack algorithm. This algorithm uses two stacks: one stack is used for operands and another one for operators.

This is code evaluating a sample expression ( ( 1 + sqrt ( 5.0 ) ) / 2.0 )

using System;
using System.Collections.Generic;

namespace ConsoleTest
{
    class Program
    {
        static void Main(string[] args)
        {
            Stack operators = new Stack();
            Stack values = new Stack(); // operands

            // An example of an arithmetic expression.
            string expr = "( ( 1 + sqrt ( 5.0 ) ) / 2.0 )";

            string[] tokens = expr.Split(" ".ToCharArray());

            foreach (string token in tokens)
            {
                switch (token)
                {
                    case "(":
                        // Ignore left parentheses.
                        break;
                    case "+":
                    case "-":
                    case "*":
                    case "/":
                    case "sqrt":
                        operators.Push(token);
                        break;
                    case ")":
                        {
                            // Pop, evaluate, and push result if token is ")".

                            // Pop an operator.
                            string op = operators.Pop();

                            // Pop the first operand.
                            double val = values.Pop();

                            switch (op)
                            {
                                // Pop the second operand and evaluate.
                                case "+":
                                    val = values.Pop() + val;
                                    break;
                                case "-":
                                    val = values.Pop() - val;
                                    break;
                                case "*":
                                    val = values.Pop() * val;
                                    break;
                                case "/":
                                    val = values.Pop() / val;
                                    break;
                                case "sqrt":
                                    val = Math.Sqrt(val);
                                    break;
                            }

                            // Push onto the operand stack the result.
                            values.Push(val);
                        }
                        break;
                    default:
                        double num;
                        if (Double.TryParse(token, out num))
                            values.Push(num);
                        else
                            throw new ArithmeticException(
                                String.Format("Expected a number. The value '{0}' is not a number.", token));
                        break;
                }
            }

            // At the end, there should be one value on the stack - the value of the expression.
            double result = values.Pop();
            Console.WriteLine("Result: {0:F5}", result);
        }
    }
}

The result is 1.61803. The above expression is evaluated in the following steps:

  • ( ( 1 + sqrt ( 5.0 ) ) / 2.0 )
  • ( ( 1 + 2.23606 ) / 2.0 )
  • ( 3.23606 / 2.0 )
  • 1.61803