Tuesday, December 27, 2011

C# Tutorial: Arithmetic Expression Evaluator

In this tutorial I use a simple algorithm that was developed by E. W. Dijkstra in the 1960s. In order to evaluate the expression, the algorithm uses two stacks: one for operands and one for operators. An expression consists of parentheses, operators, and operands (numbers). Proceeding from left to right and taking these entities one at a time, we manipulate the stacks according to four possible cases, as follows:
  • Push operands onto the operand stack.
  • Push operators onto the operator stack.
  • Ignore left parentheses.
  • On encountering a right parenthesis, pop an operator, pop the requisite number of operands, and push onto the operand stack the result of applying that operator to those operands.
After the final right parenthesis has been processed, there is one value on the stack, which is the value of the expression.
For the sake of simplicity I use a ConsoleApplication project. Add the following code to your Main() method:
// You must separate operands and operators by a white space
// Otherwise it won't work
string[] Expr = Console.ReadLine().Split(' ');
// The two stacks: one for operators and the other for operands
Stack<string> ops = new Stack<string>();
Stack<double> vals = new Stack<double>();
// The Algorithm
foreach (string item in Expr)
{
    switch (item)
    {
        // If item is operator then push 
        case "(": break;
        case "+": ops.Push(item); break;
        case "-": ops.Push(item); break;
        case "*": ops.Push(item); break;
        case "/": ops.Push(item); break;
        case "mod": ops.Push(item); break;
        case "sqrt": ops.Push(item); break;
        case "^": ops.Push(item); break;
        case ")":
            {
                // Pop, evaluate and push result if item is ")"
                string op = ops.Pop();
                double val = vals.Pop();
                switch (op)
                {
                    case "+": val += vals.Pop(); break;
                    case "-": val = vals.Pop() - val; break;
                    case "*": val *= vals.Pop(); break;
                    case "/": val = vals.Pop() / val; break;
                    case "mod": val = vals.Pop() % val; break;
                    case "sqrt": val = Math.Sqrt(val); break;
                    case "^": val = Math.Pow(vals.Pop(), val); break;
                }
                vals.Push(val);
            } break;
        // If not operator or "(" then push double value
        default: vals.Push(double.Parse(item)); break;
    }
}
// Finally, show the result
Console.Write(vals.Pop());
// Wait for user input
Console.ReadKey();
Don't forget to add spaces between operands and operators! Also you have to surround your expression with parenthesis.
That's it! You can now try to add some trig functions or whatever you want. You can also choose to parse the string differently without using space as a delimitator.

Bibliography

Robert Sedgewick, Kevin Wayne. Algorithms Fourth Edition. Pearson Education: Boston, 2011.

2 comments:

  1. Great but, I don't think it can solve this question:

    6/2(1+2)

    ReplyDelete
  2. Hi TheDarkJoker94, please add me in your Yahoo Messenger list, i wanna contact you about link-exchange, i have a website about programming too.

    My Y!M id is: kanghu_628

    ReplyDelete