Below is an implementation of a calculator web service. A problem like this is most frequently dealt with using a parse tree, and this solution is no exception. A parse tree is a binary tree representation of an expression which makes the result very easy to calculate by recursive evaluation. Our service exposes two APIs: one takes a string and returns a computed result, the other returns the parse tree for the expression for educational purposes (and to give WCF something non-trivial to marshal).
A parse tree has operators such as +, -, *, and / stored in the nodes with the children of the nodes being the operands. For example, 2 + 2 would generate the following parse tree:
+
2 2
A more complex example, 3 * 4 + 2 will result in:
+
* 2
3 4
Once a parse tree is built, the evaluation is trivial: at every node, apply evaluation recursively to the children, then perform the arithmetic operator on the results. The trick here is to build it, as its construction must account for the operator precedence, parentheses, and such.
The data structure for the node contains an operator, its two children (only would of which will be set for unary operator and in other cases), the parent, and value field used for nodes that represent values. A parenthesized subexpression lives under the separate node rooted in its right child, as illustrated below:
2 * (3 + 5) =>
*
2 ()
+
3 5
The program moves alongside the expression and adds the nodes corresponding to the tokens it parses to the tree. For example, given the following expression: 2 + 2 + 2 it will:
1) Read 2, create a value node for 2, and remember it as its current node:
2 <=
2) Read +, create an operator node for +, set node for 2 as its left child:
+ <=
2
3) Read 2, create a value node for 2, and add it to the current (+) node as its right child;
+
2 2 <=
4) Read +, create an operator node for +, set node for 2 as its left child and hooking it in place of the value node under the earlier +:
+
2 + <=
2
5) Read 2, create a value node for 2, and add it to the current (+) node as its right child;
+
2 +
2 2 <=
2 +
2 2 <=
How does the operator precedence work in this scheme? It is encoded in the tree itself. Note that the tree for 3 * 4 + 2 must be built as follows:
+
* 2
3 4
and not like this:
*
3 +
4 2
3 +
4 2
The later would treat the expression as 3 * (4 + 2), which is, of course incorrect. However, this would be the tree that a naive algorithm that just reads the next token and stuffs it into a tree would build.
To account for operator precedence, before adding a new operator node, our algorithm would look at the parent nodes of its current position and if the operator at that node has a higher precedence than the operator we are about to add, it will move up the chain and hook the new node above all the higher-precedence operators, so the tree construction for 3 * 4 * 5 + 2 will proceed like this;
3<= => *<= => * => * => * => +
3 3 4<= 3 * <= 3 * * 2
4 4 5 <= 3 *
4 5
Once this concept is clear, the rest is pure accounting (as is most of the software development :-)). The code below implements it and publishes the results through a template implementation of WCF web service, which takes on the order of 7 functional lines of code (at the very end, in the main function).
//-----------------------------------------------------------------------
//
// Copyright (C) Sergey Solyanik.
//
// This file is subject to the terms and conditions of the Microsoft Public License (MS-PL).
// See http://www.microsoft.com/opensource/licenses.mspx#Ms-PL for more details.
//
//-----------------------------------------------------------------------
using System;
using System.ServiceModel;
using System.ServiceModel.Description;
using System.Runtime.Serialization;
namespace WCFCalc
{
[ServiceContract]
public interface IWCFCalc
{
[OperationContract]
int Calculate(string expr);
[OperationContract]
ExprNode Parse(string expr);
}
public enum Operator
{
PLUS,
MINUS,
MUL,
DIV,
VAL,
EXPR,
OPENPAREN,
ERROR
}
[DataContract]
public class ExprNode
{
[DataMember]
public ExprNode Left;
[DataMember]
public ExprNode Right;
// This is not exported because the
// serialization would take it as a
// circular reference.
public ExprNode Parent;
[DataMember]
public Operator Op;
[DataMember]
public int Value;
}
public class WCFCalcSvc : IWCFCalc
{
private void Err(string s)
{
Console.WriteLine(s);
throw new FaultException
new InvalidOperationException(s), s);
}
private Operator ToOp(char c)
{
switch (c)
{
case '+': return Operator.PLUS;
case '-': return Operator.MINUS;
case '*': return Operator.MUL;
case '/': return Operator.DIV;
default: return Operator.ERROR;
}
}
private bool HigherPrecedence(Operator o1, Operator o2)
{
if ((o2 == Operator.PLUS || o2 == Operator.MINUS) &&
(o1 == Operator.MUL || o1 == Operator.DIV))
return true;
return false;
}
int Calculate(ExprNode expr)
{
if (expr.Op == Operator.VAL)
return expr.Value;
if (expr.Op == Operator.EXPR)
return Calculate(expr.Right);
if (expr.Op == Operator.PLUS)
return Calculate(expr.Left) + Calculate(expr.Right);
if (expr.Op == Operator.MINUS)
{
if (expr.Left == null)
return -Calculate(expr.Right);
return Calculate(expr.Left) - Calculate(expr.Right);
}
if (expr.Op == Operator.MUL)
return Calculate(expr.Left) * Calculate(expr.Right);
if (expr.Op == Operator.DIV)
return Calculate(expr.Left) / Calculate(expr.Right);
Err("Internal error: unknown operator!");
return 0;
}
public int Calculate(string expr)
{
return Calculate(Parse(expr));
}
public ExprNode Parse(string expr)
{
int x = 0;
ExprNode current = null;
while (x < expr.Length)
{
if (expr[x] == ' ')
{
++x;
continue;
}
if (expr[x] == '(')
{
++x;
ExprNode node = new ExprNode();
node.Op = Operator.OPENPAREN;
if (current == null)
{
current = node;
continue;
}
if ((current.Op == Operator.VAL) ||
(current.Right != null))
{
Err("Error @ " + x);
}
node.Parent = current;
current.Right = node;
current = node;
continue;
}
if (expr[x] == ')')
{
++x;
while (current != null && current.Op != Operator.OPENPAREN)
current = current.Parent;
if (current == null)
Err("Error @ " + x);
// Close the paren
current.Op = Operator.EXPR;
continue;
}
Operator op = ToOp(expr[x]);
if (op != Operator.ERROR)
{
++x;
ExprNode node = new ExprNode();
node.Op = op;
// currently no support for unary ops
if (current == null ||
(current.Op != Operator.VAL &&
current.Op != Operator.EXPR))
{
if (op == Operator.MINUS)
{
node.Parent = current;
if (current != null)
current.Right = node;
current = node;
continue;
}
Err("Error @ " + x);
}
// This ensures that the higher precedence
// operators are lower in the expression
// tree, and therefore execute before the
// lower precedence operators.
while (current.Parent != null &&
current.Parent.Op != Operator.OPENPAREN &&
!HigherPrecedence(op, current.Parent.Op))
{
current = current.Parent;
}
node.Parent = current.Parent;
if (current.Parent != null)
current.Parent.Right = node;
current.Parent = node;
node.Left = current;
current = node;
continue;
}
// value
if (expr[x] >= '0' && expr[x] <= '9')
{
int n = 0;
while (x < expr.Length && (expr[x] >= '0' && expr[x] <= '9'))
{
n = n * 10 + (expr[x] - '0');
++x;
}
ExprNode node = new ExprNode();
node.Op = Operator.VAL;
node.Value = n;
if (current == null)
{
current = node;
continue;
}
if (current.Op == Operator.VAL)
Err("Error @ " + x);
if (current.Right != null)
Err("Error @ " + x);
node.Parent = current;
current.Right = node;
current = node;
continue;
}
}
while (current != null && current.Parent != null)
{
if (current.Op == Operator.OPENPAREN)
Err("Not enough closed parens!");
current = current.Parent;
}
if (current != null && current.Op == Operator.OPENPAREN)
Err("Not enough closed parens!");
return current;
}
}
class Program
{
static void Main(string[] args)
{
Uri baseAddress = new Uri("http://localhost:8000/Calculator");
ServiceHost selfHost = new ServiceHost(typeof(WCFCalcSvc), baseAddress);
try
{
selfHost.AddServiceEndpoint(
typeof(IWCFCalc),
// DANGER! DO NOT CARRY SecurityMode.None
// INTO PRODUCTION SERVICE BY DEFAULT!!!
new WSHttpBinding(SecurityMode.None),
"Calculator");
ServiceMetadataBehavior smb = new ServiceMetadataBehavior();
smb.HttpGetEnabled = true;
selfHost.Description.Behaviors.Add(smb);
selfHost.Open();
Console.WriteLine("The service is ready.");
Console.WriteLine("Press
Console.WriteLine();
Console.ReadLine();
selfHost.Close();
}
catch (CommunicationException ce)
{
Console.WriteLine("An exception occurred: {0}", ce.Message);
selfHost.Abort();
}
}
}
}
To compile the service, create an empty console project, add System.Runtime.Serialization and System.ServiceModel to the list of references, and copy the code into it.
To consume the service, create a client project with the following code:
//-----------------------------------------------------------------------
//
// Copyright (C) Sergey Solyanik.
//
// This file is subject to the terms and conditions of the Microsoft Public License (MS-PL).
// See http://www.microsoft.com/opensource/licenses.mspx#Ms-PL for more details.
//
//-----------------------------------------------------------------------
using System;
using WCFTestClient.WCFCalc;
namespace WCFTestClient
{
class Program
{
static void Print(ExprNode n)
{
Console.Write("(" + n.Op + " ");
if (n.Left != null && n.Right != null)
{
Print(n.Left);
Console.Write(", ");
Print(n.Right);
Console.Write(")");
}
else if (n.Left != null || n.Right != null)
{
Print(n.Left != null ? n.Left : n.Right);
Console.Write(")");
}
else
{
Console.Write(n.Value + ")");
}
}
static void Main(string[] args)
{
WCFCalcClient svc = new WCFCalcClient();
for (; ; )
{
Console.Write("> ");
string s = Console.ReadLine();
if (s.Equals("exit", StringComparison.OrdinalIgnoreCase))
break;
try
{
if (s.StartsWith("p"))
{
s = s.Substring(1);
ExprNode n = svc.Parse(s);
Print(n);
Console.WriteLine();
}
else
{
Console.WriteLine(s + " = " + svc.Calculate(s));
}
}
catch (Exception e)
{
Console.WriteLine(e.Message);
}
}
}
}
}
As you can see, it only takes 1 line of code (!) to connect to our service. The rest constitutes the logic of the program itself.
Now run the service from a command line. Right-click on Service References, select "Add Service Reference", point it to http://localhost:8000/Calculator, set WCFCalc as a namespace, and click import. That's it - you are done. The service importer will create app.config with all the endpoint details, you can now just run the client.
Prefix your expression with p to display the parse tree for it, like so: p2+2, or type "exit" to leave.
2 comments:
I have no words for this great post such a awe-some information i got gathered. Thanks to Author.
From an implementation point of view, it may be a bit more flexbile to actually build a graph of your operators and have a visitor pattern traverse them. that way in the future, when you decide to add new operators (i.e. sqrt or avg) you dont need to create long IF statements.
Post a Comment