Stack In C#

What Is Stack In C#?

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 the Fibonacci Sequence, and the Factorial of a number.

The Concept -Stack Concept

To understand how a 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 order 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 popped 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(): Insert 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 elements on the stack. It's 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 be evaluated first, and the resultant value is 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 follows.

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.

using System;
using System.Collections.Generic;
public class Expression
{
    /* 
     * VARIABLES  
     */
    string expressionString;
    string postFixString;
    int result;
    Stack<int> operandStack;
    Stack<string> operatorStack;
    /*  
     * FUNCTIONS 
     */
    // Public Constructor  
    public Expression()
    {
        operandStack = new Stack<int>();
        operatorStack = new Stack<string>();
    }
    // Public Accessor Functions  
    public string ExpressionString()
    {
        return expressionString;
    }
    public int Result()
    {
        return result;
    }
    // Public Interface Functions   
    // for Expression Solving  
    public int SolveExpression()
    {
        PostFix();
        return Evaluate();
    }
    public void PostFix()
    {
        // Implementation of converting infix expression to postfix notation
        // Modify the 'postFixString' field
    }
    // Private Functions  
    private int Evaluate()
    {
        // Implementation of expression evaluation using postfix notation
        // Use the stacks and return the result
        return 0;
    }
    private bool Precedence(string oper1, string oper2)
    {
        // Implementation of checking operator precedence
        return false;
    }
    private bool IsDigit(string symbol)
    {
        // Implementation of checking if a string represents a digit
        return false;
    }
    private int Power(int a, int n)
    {
        // Implementation of calculating 'a' raised to the power 'n'
        return 0;
    }
    private int Operate(string symbol, int opnd1, int opnd2)
    {
        // Implementation of performing the arithmetic operation
        return 0;
    }
}

The SolveExpression() is a function that is exposed to the user. It internally makes a call to the PostFix() and subsequently Evaluates () functions to eventually evaluate an expression.

Creation of the PostFixString

For creating the postfix string for a given mathematical expression, we require 2 stacks, namely.

OperandStack
peratorStack

The code snippet converts an expression string from the default(infix) to a postfix expression.

publicvoid 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 the 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 operand stack in postfix order. On executing the PostFix() for the expression 4*(6/3), the following would be the contents of both the stack.

At the end of the PostFix Function Contents of both Stacks are.

Stack In C#

Remark 3. The OperandStack is merely used for creating the postFix order. Hence the postfix string is appended whenever an element is pushed onto the operand stack.

Note that the postfix string contains exactly the contents of the OperandStack. Both the Stacks can now be freed since we have the postfix string stored in a variable.

Evaluation of PostFix Expression

Once the postfix string is created, the following Code Snippet evaluates the expression.

privateint 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()

Remark 4

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 incorporate 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.