Thursday, June 9, 2011

Numeric and Boolean Expression Parser Using Conversion From Infix to Postfix using C#

Dears

Below is a source code to the expression parser with ability to parse combined expressions, that is numeric and booleans, and variable support. See Main method for demo purposes.


Code Snippet
  1. using System;
  2. using System.Collections.Generic;
  3.  
  4. public class ExpressionEvaluator
  5. {
  6.     #region class AtomicExpression
  7.     /// <summary>
  8.     /// This class holds atomic expressions. It holds either variables, values or operators.
  9.     /// If the class holds operator, it can provide result given the input values
  10.     /// </summary>
  11.     public class AtomicExpression
  12.     {
  13.         private string _value;
  14.  
  15.         /// <summary>
  16.         /// Parsed value of the strig value used during evaluation
  17.         /// </summary>
  18.         public object ParsedValue { get; set; }
  19.  
  20.         /// <summary>
  21.         /// Value of the current expression
  22.         /// It is either numeric value or name of the variable (e.g. 1, A, Aleph)
  23.         /// </summary>
  24.         public string Value
  25.         {
  26.             get
  27.             {
  28.                 return _value;
  29.             }
  30.             set
  31.             {
  32.                 double outd;
  33.                 if (double.TryParse(value, out outd)) {
  34.                     ParsedValue = outd;
  35.                 }
  36.                 bool outb;
  37.                 if (bool.TryParse(value, out outb)) {
  38.                     ParsedValue = outb;
  39.                 }
  40.                 _value = value;
  41.             }
  42.         }
  43.         /// <summary>
  44.         /// String representation of the operator (e.g. '==' or '||')
  45.         /// </summary>
  46.         public string Operator { get; set; }
  47.  
  48.         /// <summary>
  49.         /// Evaluates the unary operator with provided value
  50.         /// </summary>
  51.         /// <param name="value">Value for unary operator</param>
  52.         /// <returns>Evaluated expression of the unary operator</returns>
  53.         public object Evaluate(object value)
  54.         {
  55.             if (Operator == "!") {
  56.                 return !((bool)value);
  57.             }
  58.             throw new NotImplementedException(Operator + " operator not implemented");
  59.         }
  60.  
  61.         /// <summary>
  62.         /// Evaluates the binary operator expression with provided values
  63.         /// </summary>
  64.         /// <param name="val1">Left-side value for the operator</param>
  65.         /// <param name="val2">Right-side value for the operator</param>
  66.         /// <returns>Output value of the binary expression</returns>
  67.         public object Evaluate(object val1, object val2)
  68.         {
  69.             Console.Write("{0} {1} {2} = ", val1, Operator, val2);
  70.             switch (Operator) {
  71.                 case "+":
  72.                     return (double)val1 + (double)val2;
  73.                 case "-":
  74.                     return (double)val1 - (double)val2;
  75.                 case "*":
  76.                     return (double)val1 * (double)val2;
  77.                 case "/":
  78.                     return (double)val1 / (double)val2;
  79.                 case ">":
  80.                     return (double)val1 > (double)val2;
  81.                 case ">=":
  82.                     return (double)val1 >= (double)val2;
  83.                 case "<":
  84.                     return (double)val1 < (double)val2;
  85.                 case "<=":
  86.                     return (double)val1 <= (double)val2;
  87.                 case "==":
  88.                     return (double)val1 == (double)val2;
  89.                 case "!=":
  90.                     return (double)val1 != (double)val2;
  91.                 case "&&":
  92.                     return (bool)val1 && (bool)val2;
  93.                 case "||":
  94.                     return (bool)val1 || (bool)val2;
  95.  
  96.             }
  97.             throw new NotImplementedException(Operator + " operator not implemented");
  98.         }
  99.  
  100.         public override string ToString()
  101.         {
  102.             return string.Format("{0}{1}", Value, Operator);
  103.         }
  104.     }
  105.     #endregion
  106.  
  107.     #region Evaluate(List<AtomicExpression> list, Dictionary<string, object> variables)
  108.     /// <summary>
  109.     /// Evaluates the input AtomicExpression (see AtomicExpression) list with the list of provided variables
  110.     /// and calculates the numeric or boolean output. List of expressions is sorted in infix order.
  111.     /// </summary>
  112.     /// <param name="list">List of input expressions. Expressions are evaluated in the postfix manner.</param>
  113.     /// <param name="variables">List of variables and their values used during the evaluation</param>
  114.     /// <returns></returns>
  115.     public object Evaluate(List<AtomicExpression> list, Dictionary<string, object> variables)
  116.     {
  117.         var stack = new Stack<object>();
  118.  
  119.         foreach (var expression in list) {
  120.             // double value
  121.             if (expression.ParsedValue != null) {
  122.                 stack.Push(expression.ParsedValue);
  123.                 continue;
  124.             }
  125.             // variable
  126.             if (!string.IsNullOrEmpty(expression.Value)) {
  127.                 stack.Push(variables[expression.Value]);
  128.                 continue;
  129.             }
  130.             // unary operator
  131.             object result;
  132.             if (expression.Operator == "!") {
  133.                 result = expression.Evaluate(stack.Pop());
  134.                 Console.WriteLine(result);
  135.             }
  136.                 // binary operator
  137.             else {
  138.                 var p2 = stack.Pop();
  139.                 var p1 = stack.Pop();
  140.                 result = expression.Evaluate(p1, p2);
  141.                 Console.WriteLine(result);
  142.             }
  143.             stack.Push(result);
  144.         }
  145.         Console.WriteLine("Result: " + stack.Peek());
  146.         return stack.Pop();
  147.     }
  148.     #endregion
  149.  
  150.     #region CheckParenthesis(string expression)
  151.     /// <summary>
  152.     /// Checks if given expression is well formed with parenthesis
  153.     /// </summary>
  154.     /// <param name="expression">Input expression (e.g. A+B-(2*2)>0)</param>
  155.     /// <returns></returns>
  156.     public virtual bool CheckParenthesis(string expression)
  157.     {
  158.         var stack = new Stack<string>();
  159.  
  160.         foreach (var c in expression) {
  161.             switch (c) {
  162.                 case '(':
  163.                     stack.Push(c.ToString());
  164.                     break;
  165.                 case ')':
  166.                     if (stack.Count == 0) {
  167.                         return false;
  168.                     }
  169.                     stack.Pop();
  170.                     break;
  171.             }
  172.         }
  173.         return stack.Count <= 0;
  174.     }
  175.     #endregion
  176.  
  177.     #region List<AtomicExpression> Postfix(string expression)
  178.     /// <summary>
  179.     /// Converts the input infix expression into the postfix and creates the list
  180.     /// of atomic expressions in this infix order
  181.     /// </summary>
  182.     /// <param name="expression">Infix expression (e.g. A+B-(2*2)>0||B)</param>
  183.     /// <returns>List of atomic expressions sorted in the infix order</returns>
  184.     public virtual List<AtomicExpression> Postfix(string expression)
  185.     {
  186.         var expressions = new List<AtomicExpression>();
  187.         var variable = string.Empty;
  188.         var stack = new Stack<string>();
  189.         // remove spaces
  190.         expression = expression.Replace(" ", string.Empty);
  191.         char c;
  192.         string sc;
  193.  
  194.         for (var i = 0; i < expression.Length; i++) {
  195.             c = expression[i];
  196.  
  197.             // variable or number
  198.             if (char.IsLetterOrDigit(c)) {
  199.                 variable += c;
  200.             }
  201.                 // left parthesis
  202.             else if (c == '(') {
  203.                 stack.Push(c.ToString());
  204.             }
  205.                 // right parenthesis
  206.             else if (c == ')') {
  207.                 // add variable
  208.                 if (!string.IsNullOrEmpty(variable)) {
  209.                     expressions.Add(new AtomicExpression { Value = variable });
  210.                 }
  211.                 variable = string.Empty;
  212.                 while (!stack.Peek().Equals("(")) {
  213.                     expressions.Add(new AtomicExpression { Operator = stack.Pop() });
  214.                 }
  215.                 stack.Pop();
  216.             }
  217.                 // operator
  218.             else {
  219.                 sc = c.ToString();
  220.  
  221.                 // add variable
  222.                 if (!string.IsNullOrEmpty(variable)) {
  223.                     expressions.Add(new AtomicExpression { Value = variable });
  224.                 }
  225.                 variable = string.Empty;
  226.  
  227.                 // check for operators having 2 characters
  228.                 if (i < expression.Length - 1 && !char.IsLetterOrDigit(expression[i + 1]) && expression[i + 1] != '(' && expression[i + 1] != ')') {
  229.                     sc += expression[i + 1];
  230.                     i++;
  231.                 }
  232.                 // add all expressions with higher or same priority
  233.                 while (stack.Count > 0 && Priority(stack.Peek()) >= Priority(sc)) {
  234.                     expressions.Add(new AtomicExpression { Operator = stack.Pop() });
  235.                 }
  236.                 stack.Push(sc);
  237.             }
  238.         }
  239.         while (stack.Count > 0) {
  240.             expressions.Add(new AtomicExpression { Operator = stack.Pop() });
  241.         }
  242.         return expressions;
  243.     }
  244.     #endregion
  245.  
  246.  
  247.     // main method
  248.  
  249.     #region Main(string[] args)
  250.     public static void Main(string[] args)
  251.     {
  252.         ExpressionEvaluator s = new ExpressionEvaluator();
  253.         var list = s.Postfix("A && !(B > 2 + 1) || ( !A && !(B==2))");
  254.  
  255.         Console.WriteLine("------------------------------------------");
  256.         foreach (var expression in list) {
  257.             Console.Write(expression.ToString());
  258.         }
  259.         Console.WriteLine("\r\n------------------------------------------");
  260.         var dict = new Dictionary<string, object>();
  261.         dict.Add("A", true);
  262.         dict.Add("B", 3d);
  263.         s.Evaluate(list, dict);
  264.         Console.ReadKey();
  265.     }
  266.     #endregion
  267.  
  268.     // private methods
  269.  
  270.     #region Priority(string x)
  271.     private static int Priority(string x)
  272.     {
  273.         if (x.Equals("||"))
  274.             return 0;
  275.         if (x.Equals("&&"))
  276.             return 1;
  277.         if (x[0].Equals('<') || x[0].Equals('>') || x[0].Equals('=') || x[0].Equals('!'))
  278.             return 2;
  279.         if (x.Equals("+") || x.Equals("-"))
  280.             return 3;
  281.         if (x.Equals("*") || x.Equals("/"))
  282.             return 4;
  283.         if (x.Equals("(") || x.Equals(")"))
  284.             return -1;
  285.         throw new NotImplementedException(x + " is not implemented");
  286.     }
  287.     #endregion
  288. }

2 comments:

DimiS said...

use just "A" as expresion string - it woun't work
also double not (!!A)
also negation (-A)
also you cant compare two boolean (A>B == C)

but anyway thanks, i'm using it with those bugs fixed and some functonality stripped out

Anonymous said...

Any chance you can contribute back the code? I am working on making it handle variable names longer than one character and do string comparisons as well. Thanks.