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 in 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)
C# Experiments: Arithmetic Expression Compiler (Part 2)
C# Experiments: Arithmetic Expression Compiler (Part 3)
C# Experiments: Arithmetic Expression Compiler (Part 4)
C# Experiments: Arithmetic Expression Compiler (Part 5)
C# Experiments: Arithmetic Expression Compiler (Part 6)
C# Experiments: Arithmetic Expression Compiler (Part 7)
C# Experiments: Arithmetic Expression Compiler (Part 8)
C# Experiments: Arithmetic Expression Compiler (Part 9)
C# Experiments: Arithmetic Expression Compiler (Part 10)
C# Experiments: Arithmetic Expression Compiler (Part 11)
The code typed-in during the interview series is as follows for your reference:
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)
{
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)";
if (CheckExp(inputExp))
{
inputExp = FormattedExpression(inputExp);
MessageBox.Show(ExpressionEvaluator(inputExp));
}
else
MessageBox.Show("The expression isn't in the proper format.");
}
public bool CheckExp(string exp)
{
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() == '+')
{
numberStack.Push(numberStack.Pop() + numberStack.Pop());
operatorStack.Pop();
}
else if (operatorStack.Peek() == '*')
{
numberStack.Push(numberStack.Pop() * numberStack.Pop());
operatorStack.Pop();
}
else if (operatorStack.Peek() == '/')
{
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]))
{
while (i != exp.Length && digits.Contains(exp[i]))
i++;
if(i == exp.Length || exp[i] != ')')
exp = exp.Insert(i, ")");
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] == '(')
{
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.
Go to C# Experiments to access more of such content! Thanks again!
This member has not yet provided a Biography. Assume it's interesting and varied, and probably something to do with programming.