Stack in C#

Introduction

Stacks are one of the common data structures used in the software world, which follows the First In Last Out paradigm. Stacks are used in various mathematical functions like Towers of Hanoi , finding Fibonacci Sequence , Factorial of a number to name a few. Currently, we focus on Evaluating a mathematical expression using Stacks.
The Concept

Stack Concept

To understand the working of Stacks consider for example the data elements:
Data Elements : A , B , C
 
In the above example, data elements were entered in the following order A,B,C. In Stack Terminology the elements were pushed in the following order A, B, C.

StackPush Order = A, B, C
Also, we have StackTop = C

Now, if we consider removing the elements also known as popping the element from the stack
StackPop Order = C, B, A
Notice that the StackPop is exactly the reverse of the order in which the data elements were popped.
Thus the most important operations on the Stack Data Structure are:

• Push()                  : Inserting an element onto the Stack
• TopOfStack()        : Reading the element on Top of the Stack
• Pop()                   : Removing the topmost element from the Stack
• IsEmpty()             : This operation checks if there are any data element on the stack. Its required to
                              avoid StackPop() when there are no elements on the Stack.

There are other operations viz. Total Number of Elements etc defined which are available in C#

Expression Concept

Stacks can be used to solve mathematical expressions like X + Y and produce the resultant Z.

X + Y = Z
To solve an expression using stacks, the string is first transformed into a postfix string expression:
For example consider the expression
Expression : X + Y * Z
Here, in the above case precedence of operators is used as thumb rules for solving an expression. We need to specify that Y * Z to be evaluated first and the resultant value be added to X. Converting a string into postfix form is a means by which we can achieve the necessary precedence of operators in expression solving.
Postfix String : X Y Z * +
Implementation of Stack for solving an Expression

Following is the Application Snapshot which solves an Expression and displays the Results.
The output using WinForms appears as follows:
 
An outline of the algorithm for solving an expression is as follows:

• Accept the mathematical expression in string format
• Generate the PostFix string of the entered expression.
• Evaluate the expression to arrive at the Result of the Expression

Implementation

1) A Class called the Expression Class is defined to represent the mathematical Expression to be solved.
Given below is an overview of the Class Expression using which a mathematical expression can be solved.

//public class Expression
{
/*
* VARIABLES
*/
String expressionString;
String postFixString ;
int result ;
Stack operandStack ;
Stack operatorStack ; 
/*
* FUNCTIONS
*/
// Public Constructor
public Expression()
// Public Accessor Functions
public string ExpressionString()
public int Result()
// Public Interface Functions
// for Expression Solving
public int SolveExpression()
public void PostFix()
// Private Functions
private int Evaluate()
private bool precedence(string oper1, string oper2)
private bool isdigit(string symbol)
private int power(int a , int n )
private int operate(string symbol, int opnd1, int opnd2)
} // end of Expression Class

2) The SolveExpression() is a function that is exposed to the user. It internally makes a call to the PostFix() and subsequently Evaluate() functions to eventually evaluate an expression.
3) Creation of the PostFixString : For creating the postfix string for a given mathematical expressions we require 2 stacks namely :

• OperandStack
• peratorStack

Code snippet that converts an expression string from default(infix) to postfix expression :


public void PostFix()
{
int index = 0 ;
string c = "";
string topSymb = "";
this.postFixString = "";
while (index < this.ExpressionString.Length )
{
c = this.expressionString.Substring(index, 1 );
if(isdigit(c))
{
this.operandStack.Push(c);
this.postFixString += this.operandStack.Peek().ToString();
}
else
{
while(this.operatorStack.Count !=0 &&
this.precedence(this.operatorStack.Peek().ToString(),c))
{
if((this.operatorStack.Peek().ToString() == "(") ||
(this.operatorStack.Peek().ToString() == ")"))
{
topSymb = this.operatorStack.Pop().ToString();
continue ;
}
else
{
topSymb = this.operatorStack.Pop().ToString();
this.operandStack.Push(topSymb);
this.postFixString += this.operandStack.Peek().ToString();
}// end of Stack Peek else
}// end of while
this.operatorStack.Push(c);
}//end of isdigit() else
index++;
} // end of while
int nochange = 0 ;
while(this.operatorStack.Count !=0)
{
if((this.operatorStack.Peek().ToString() == "(") ||
(this.operatorStack.Peek().ToString() == ")"))
{
topSymb = this.operatorStack.Pop().ToString();
continue ;
}
else
{
topSymb = this.operatorStack.Pop().ToString();
this.operandStack.Push(topSymb);
this.postFixString += this.operandStack.Peek().ToString();
}// end of StackPeek else
}// end of while
}//end of PostFix()

Remark 1 :

The current example supports the following operators :
' + ' ,' - ', '*', ' / ' , '(' , ')' , ' $ ' , where all the operators have their usual meaning except for ' $ ' which represents exponentiation operator.
Remark 2 :

The above code parses the input Expression string and creates the postFix string. Actually, the input expression string is pushed onto the operandStack in postfix order. On executing the PostFix() for the expression 4*(6/3) the following would be the contents of the both the stack :
At the end of PostFix Function Contents of both the Stacks are :



Remark 3 :

The OperandStack is merely used for creating the postFix order. Hence the postFixString is appended whenever an element is pushed onto the OperandStack.
Note that the postFixString contains exactly the contents of the OperandStack. Both the Stack can now be freed since we have the postFixString stored in a variable.
4) Evaluation of PostFix Expression
Once the postFixString is created the following Code Snippet evaluates the expression :
private int Evaluate()
{
string c = "";
int opnd1=0, opnd2=0, dataValue =0 ;
int index = 0 ;
this.operandStack = new Stack() ;
while (index < this.postFixString.Length )
{
c = this.postFixString.Substring(index, 1 );
if(isdigit(c))
{
this.operandStack.Push(c);
} // end of if(isdigit)
else
{
try
{
opnd2 =Int32.Parse(this.operandStack.Pop().ToString());
opnd1 = Int32.Parse(this.operandStack.Pop().ToString());
if (opnd1 == 0 && opnd2 == 0)
{
dataValue = 0 ;
}
else
{
dataValue = operate(c,opnd1, opnd2);
} // end of try
}
catch
{
}
this.operandStack.Push(dataValue);
} //end of isdigit(else)
index++ ;
} //end of while
return dataValue;
} // end of Evaluate()

Remarks:

• The above code parses the PostFix string to solve the Expression.
• Each time it encounters an operand it pushes the data onto the OperandStack(we require only one stack here).
• When it encounters an operator it pops the top two operands ,applies the operator and pushes the result back onto the Stack
• This process terminates once the entire postFix string is evaluated.
• The Code Files are attached for reference.

Drawbacks of the System

The System currently only supports single - digit decimal operands. Also the system doesn't incorporated nested braces.
Conclusion

The above illustration demonstrates only one of the many examples that stacks can be used for. It also demonstrates how in-built DATA STRUCTURES can be used for effective Application Programming.