Stack In C#

C# Stack Introduction

 
Stacks are one of the common data structures used in programming. A stack data structure uses the first-in-last-out process. Some of the common stack coding examples are Towers of Hanoi, finding Fibonacci Sequence, and Factorial of a number. 

The Concept - Stack Concept


To understand how stack works, consider for example the data elements.

Data Elements : A, B, C

Stack In C# 
In the above example, data elements were inserted in the following order A, B, and C. In Stack terms, the elements were pushed on the stack in oder A, B, and C. Adding elements to a stack is called Push.

StackPush Order = A, B, C

Also, we have StackTop = C.

Now, if we consider removing any elements of a stack, the process is called Pop. In stack terms, an element is poped from the stack. The removal of elements of a stack is done in first-in-last-out order. It means, the most recently added element will be the first one to pop from a stack.
 
StackPop Order = C, B, A

Notice that the StackPop is exactly the reverse of the order in which the data elements were popped.

The most important operations on stack data structure are:
  • Push() : Inserting an element onto the stack
  • TopOfStack() : Reading the element on the 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.

Expression Concept


A stack 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, the 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 an application UI that solves an expression and displays the result.

Stack In C# 

An outline of the algorithm for solving an expression is as following:
  • Accept a mathematical expression in string format
  • Generate the PostFix string of the entered expression
  • Evaluate the expression and generate a result

 

Implementation

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.

 

  1. //public class Expression  
  2. {  
  3.     /* 
  4.      * VARIABLES  
  5.      */  
  6.     String expressionString;  
  7.     String postFixString;  
  8.     int result;  
  9.     Stack operandStack;  
  10.     Stack operatorStack;  
  11.     /*  
  12.      * FUNCTIONS 
  13.      */  
  14.     // Public Constructor  
  15.     public Expression()  
  16.     // Public Accessor Functions  
  17.     publicstring ExpressionString()  
  18.     publicint Result()  
  19.     // Public Interface Functions   
  20.     // for Expression Solving  
  21.     publicint SolveExpression()  
  22.     publicvoid PostFix()  
  23.     // Private Functions  
  24.     privateint Evaluate()  
  25.     privatebool precedence(string oper1, string oper2)  
  26.     privatebool isdigit(string symbol)  
  27.     privateint power(int a, int n)  
  28.     privateint operate(string symbol, int opnd1, int opnd2)  
  29. // end of Expression Class  
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.
 

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,

  1. publicvoid PostFix() {  
  2.     int index = 0;  
  3.     string c = "";  
  4.     string topSymb = "";  
  5.     this.postFixString = "";  
  6.     while (index < this.ExpressionString.Length) {  
  7.         c = this.expressionString.Substring(index, 1);  
  8.         if (isdigit(c)) {  
  9.             this.operandStack.Push(c);  
  10.             this.postFixString += this.operandStack.Peek().ToString();  
  11.         } else {  
  12.             while (this.operatorStack.Count != 0 && this.precedence(this.operatorStack.Peek().ToString(), c)) {  
  13.                 if ((this.operatorStack.Peek().ToString() == "(") || (this.operatorStack.Peek().ToString() == ")")) {  
  14.                     topSymb = this.operatorStack.Pop().ToString();  
  15.                     continue;  
  16.                 } else {  
  17.                     topSymb = this.operatorStack.Pop().ToString();  
  18.                     this.operandStack.Push(topSymb);  
  19.                     this.postFixString += this.operandStack.Peek().ToString();  
  20.                 } // end of Stack Peek else  
  21.             } // end of while   
  22.             this.operatorStack.Push(c);  
  23.         } //end of isdigit() else   
  24.         index++;  
  25.     } // end of while   
  26.     int nochange = 0;  
  27.     while (this.operatorStack.Count != 0) {  
  28.         if ((this.operatorStack.Peek().ToString() == "(") || (this.operatorStack.Peek().ToString() == ")")) {  
  29.             topSymb = this.operatorStack.Pop().ToString();  
  30.             continue;  
  31.         } else {  
  32.             topSymb = this.operatorStack.Pop().ToString();  
  33.             this.operandStack.Push(topSymb);  
  34.             this.postFixString += this.operandStack.Peek().ToString();  
  35.         } // end of StackPeek else   
  36.     } // end of while   
  37. //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,

Stack In C#
Stack In C#

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.

Evaluation of PostFix Expression


Once the postFixString is created the following Code Snippet evaluates the expression,
  1. privateint Evaluate() {  
  2.     string c = "";  
  3.     int opnd1 = 0, opnd2 = 0, dataValue = 0;  
  4.     int index = 0;  
  5.     this.operandStack = new Stack();  
  6.     while (index < this.postFixString.Length) {  
  7.         c = this.postFixString.Substring(index, 1);  
  8.         if (isdigit(c)) {  
  9.             this.operandStack.Push(c);  
  10.         } // end of if(isdigit)  
  11.         else {  
  12.             try {  
  13.                 opnd2 = Int32.Parse(this.operandStack.Pop().ToString());  
  14.                 opnd1 = Int32.Parse(this.operandStack.Pop().ToString());  
  15.                 if (opnd1 == 0 && opnd2 == 0) {  
  16.                     dataValue = 0;  
  17.                 } else {  
  18.                     dataValue = operate(c, opnd1, opnd2);  
  19.                 } // end of try   
  20.             } catch {}  
  21.             this.operandStack.Push(dataValue);  
  22.         } //end of isdigit(else)  
  23.         index++;  
  24.     } //end of while  
  25.     return dataValue;  
  26. // 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.