C# Experiments: Interview Series – Arithmetic Expression Compiler

Number crunching software dates back to the dawn of computing. It has been fine-tuned and updated with innumerable features till date.

Here in this setup of an Interview, we’ll use Djikstra’s Two-Stack Algorithm at its core to build a simple Arithmetic Expression Compiler that can Multiply, Divide, and Add non-negative N-Digit Rational numbers together following Operator precedence of the BODMAS rule.

Before starting to evaluate our expression, we define a function that checks for the validity of the expression; i.e., whether there are equal number of opening & closing parenthesis, whether the parenthesis are in the right order and properly fitted amongst numbers; whether there are no invalid characters in our expression, etc.

The key idea in Djikstra’s Two-Stack algorithm is to maintain 2 stacks; one for the numbers and the other for the operators. The algorithm works by popping out the latest two numbers in the Number-stack and perform the operation according to what’s present at the top of the Operator-stack. The operator is popped out after that and the result is pushed back into the Number-Stack.

The Two-Stack algorithm works best for two numbers at a time. The algorithm needs to be guided about Operator precedence as well. To implement our Arithmetic Expression Compiler following this algorithm, we need to modify our Input expression is such a way that all of this are taken care off.

According to BODMAS rule, Brackets have the highest precedence over all operators. This fact can be exploited to our advantage by encircling the numbers with braces to get the precedence right! In our FormattedExpression function, we cover many scenarios to generate closing braces ‘)’ in our expression to follow proper precedence.

Our ExpressionEvaluator function will take in the refined Input expression as a parameter and returns the final answer. By passing over all the characters in our refined input expression, we can push operators and numbers to their respective stacks accordingly. When we encounter a ‘)’ in our expression, we call our Two-Stack algorithm implementation.

In this interview, we won’t be covering evaluating negative numbers and the subtraction operation. The overhead and complexity involved is high and it would be great if you can take it up as an exploratory activity. One of the challenges involved is to know when the ‘-’ sign is used as an operator or for a negative number; besides, when the output of a sub-expression in brackets return a negative number, the operator present to the left of the ‘(’ bracket of that sub-expression would be chained along with the negative sign of the number! There are many other issues involved.

Please check out the 10 video-links where I go through this simulated interview in much more detail.

C# Experiments: Arithmetic Expression Compiler (Part 1)

The code typed-in during the interview series is as follows for your reference:-

    //Djikstra's Two-Stack Algorithm
    List<char> operators = new List<char> { '+', '*', '/'};
    List<char> digits = new List<char> { '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', '.' };

    Stack<char> operatorStack = new Stack<char>();
    Stack<double> numberStack = new Stack<double>();
    StringBuilder numBuilder = new StringBuilder();

    private void button1_Click(object sender, EventArgs e)
    {
        //Phase #1:-
        //Operators: +, *, /
        //No BODMAS rule
        //Non-Negative 1-Digit Intergral Numbers: 0 to 9.

        //Phase #2:-
        //Implement the 'B' in BODMAS Rule.
        //Non-Negative N-Digit Rational Numbers.

        //Phase #3:-
        //Implement "DMA" in BODMAS Rule.

        //Phase #4:-
        //Check for the legitimacy of the expression.

        //Phase #5:- [Exploratory]
        //Evaluate Subtraction operation.
        //Accommodate negative N-Digit Rational Numbers.

        //3*4*2/5 => (((3*4)*2)/5) => 3*4)*2)/5)

        //string inputExp = "(3*5)/10";

        //string inputExp = "5*7/4*2+1+3*6+2+1"; //Output is 39.5
        //string inputExp = "2*((3+4)*((2+7)*2+4*(5+1)))"; //Output is 588
        //string inputExp = "50*70/40*(2+5)+50*70/40*(5+1)+3*(66+2/3)+3*(6*2+2)+50*70/40"; //Output is 1467
        string inputExp = "(2.9+5.3)+50.45*70.90/40.65/(5.2+1.5)+3.7*(66.2+2.5/3.4)+3.2*(6.3+6.7*2.3+2.6)"; //Output is 346.78..

        if (CheckExp(inputExp))
        {
            inputExp = FormattedExpression(inputExp);

            MessageBox.Show(ExpressionEvaluator(inputExp));

            //double ans = (3.0 * 5.0) / 10.0;
            //MessageBox.Show(ans.ToString());
        }
        else
            MessageBox.Show("The expression isn't in the proper format.");

    }

    public bool CheckExp(string exp)
    {
        //[Regex]
        //Check if exp has no character other than:-
        // 0,1,2,3,4,5,6,7,8,9,., ,+,*,/,(,).

        //[Regex().Matches().Count]
        //Check if the number of '(' and ')' are equal.

        //[Scan from L->R and Track Stack population]
        //Check the tracker when calling ArithmeticComputation() [When exp[i] == ')']
        //There must be atleast 1 operator and 2 numbers within any '(' & ')'.

        //[Regex]
        //Only a number or '(' must be present immediately after an '('.

        //[Regex]
        //Only a number or ')' must be present immediately before a ')'.

        //[Regex]
        //No operator must be present immediately before & after any operator.

        //[catch DivisionByZero Exception]
        //Add a check for division by 0 in the ArithmeticComputation() function.

        //[TryParse]
        //Check whether numbuilder has a legitimate number.
        //This can be done just before pushing a number into the numberStack.

        return true;
    }

    public string ExpressionEvaluator(string exp)
    {
        for (int i = 0; i < exp.Length; i++)
        {
            if (operators.Contains(exp[i]))
                operatorStack.Push(exp[i]);

            else if (digits.Contains(exp[i]))
            {
                while (i != exp.Length && digits.Contains(exp[i]))
                    numBuilder.Append(exp[i++]);

                numberStack.Push(Convert.ToDouble(numBuilder.ToString()));
                numBuilder.Clear();
                i--;
            }

            else if (exp[i] == ')')
                ArithmeticComputation();
        }

        while (numberStack.Count != 1 && operatorStack.Count != 0)
            ArithmeticComputation();

        return Convert.ToString(numberStack.Pop());
    }

    public void ArithmeticComputation()
    {
        if (operatorStack.Peek() == '+')
        {
            //'+' is Commutative
            numberStack.Push(numberStack.Pop() + numberStack.Pop());
            operatorStack.Pop();
        }

        else if (operatorStack.Peek() == '*')
        {
            //'*' is Commutative
            numberStack.Push(numberStack.Pop() * numberStack.Pop());
            operatorStack.Pop();
        }

        else if (operatorStack.Peek() == '/')
        {
            //'/' is NOT Commutative
            double divisor = numberStack.Pop();
            numberStack.Push(numberStack.Pop() / divisor);
            operatorStack.Pop();
        }

    }

    public string FormattedExpression(string exp)
    {
        int temp = 0;
        for (int i = 0; i < exp.Length; i++)
        {
            if (exp[i] == '*' || exp[i] == '/')
            {
                temp = i;
                i++;

                if (digits.Contains(exp[i]))
                {
                    //2+3*5+1 => 2+(3*5)+1 => 2+3*5)+1
                    //2+(3*5)/4 => 2+(3*5))/4) is wrong!
                    //When there's a number after '*' or '/'
                    //and the character after that number is not a ')'
                    //put a ')' after that number without any more checks.

                    while (i != exp.Length && digits.Contains(exp[i]))
                        i++;

                    if(i == exp.Length || exp[i] != ')')
                        exp = exp.Insert(i, ")");

                    //(2+233*5)/4 => ((2+(3*5))/4) => 2+3*5))/4)

                    //When there's a number after '*' or '/'
                    //and the character after that number is a ')'
                    //and the character at the beginning of the number before the '*' or '/' is not a '('
                    //put a ')' after that number.
                    else if (exp[i] == ')')
                    {
                        while (temp != 0 && digits.Contains(exp[temp - 1]))
                            temp--;

                        if (temp == 0 || exp[temp - 1] != '(')
                            exp = exp.Insert(i, ")");
                    }

                }
                else if (exp[i] == '(')
                {
                    //2*(3+6)/4 => 2*3+6))/4)
                    //(2*(3+6))+4 => (2*(3+6)))+4 is wrong. 2*3+6))+4 is correct.
                    //2*((3+4)+7) => 2*(3+4))+7) is wrong. 2*3+4)+7) is correct.
                    //When there's a '(' after '*' or '/'
                    //and the character at the beginning of the number before the '*' or '/' is not a '('
                    //and there are no inner sub-expressions surrounded by braces.
                    //put a ')' at the end of terms encircled by the brackets

                    int temp2 = i;

                    while (temp != 0 && digits.Contains(exp[temp - 1]))
                        temp--;

                    if (temp == 0 || exp[temp - 1] != '(')
                    {
                        var braceStack = new Stack<char>();
                        var innerCurls = false;

                        for (int j = temp2; j < exp.Length; j++)
                        {
                            if (exp[j] == '(')
                            {
                                braceStack.Push('(');
                                if (braceStack.Count == 2)
                                    innerCurls = true;
                            }

                            else if (exp[j] == ')')
                                braceStack.Pop();

                            if (innerCurls)
                                break;

                            if (braceStack.Count == 0 && !innerCurls)
                            {
                                exp = exp.Insert(j + 1, ")");
                                break;
                            }

                        }

                    }

                }

            }
        }
        return exp;
    }

Thank you for reading this post and watching the videos. Please Subscribe, Comment and Rate the Channel if you liked the videos.

Goto C# Experiments to access more of such content! Thanks again!

C# Experiments

Sunday 30 June 2013

Interview Series – Arithmetic Expression Compiler

No comments:

Post a Comment