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 VB.Net.
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
'
Private expressionString As String
Private postFixString As String
Private result As Integer
Private operandStack As Stack
Private operatorStack As Stack
'
'* FUNCTIONS
'
' Public Constructor
public Expression()
' Public Accessor Functions
public String ExpressionString()
public Integer Result()
' Public Interface Functions
' for Expression Solving
public Integer SolveExpression()
public void PostFix()
' Private Functions
private Integer Evaluate()
private Boolean precedence(String oper1, String oper2)
private Boolean isdigit(String symbol)
private Integer power(Integer a, Integer n)
private Integer operate(String symbol, Integer opnd1, Integer opnd2)
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
- OperatorStack
Code snippet that converts an expression string from default(infix) to postfix expression :
Public Sub PostFix()
Dim index As Integer = 0
Dim c As String = ""
Dim topSymb As String = ""
Me.postFixString_Renamed = ""
Do While index < Me.ExpressionString.Length
c = Me.expressionString_Renamed.Substring(index, 1)
If isdigit(c) Then
Me.operandStack.Push(c)
Me.postFixString_Renamed &= Me.operandStack.Peek().ToString()
Else
Do While Me.operatorStack.Count <>0 AndAlso Me.precedence
Me.operatorStack.Peek().ToString(),c)
If (Me.operatorStack.Peek().ToString() = "(") OrElse (Me.operatorStack.Peek().ToString() = ")") Then
topSymb = Me.operatorStack.Pop().ToString()
GoTo Continue1
Else
topSymb = Me.operatorStack.Pop().ToString()
Me.operandStack.Push(topSymb)
Me.postFixString_Renamed &= Me.operandStack.Peek().ToString()
End If ' end of Stack Peek else
Continue1:
Loop ' end of while
Me.operatorStack.Push(c)
End If 'end of isdigit() else
index += 1
Loop ' end of while
Dim nochange As Integer = 0
Do While Me.operatorStack.Count <>0
If (Me.operatorStack.Peek().ToString() = "(") OrElse (Me.operatorStack.Peek().ToString() = ")") Then
topSymb = Me.operatorStack.Pop().ToString()
GoTo Continue2
Else
topSymb = Me.operatorStack.Pop().ToString()
Me.operandStack.Push(topSymb)
Me.postFixString_Renamed &= Me.operandStack.Peek().ToString()
End If ' end of else
Continue2:
Loop ' end of while
End Sub '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 Function Evaluate() As Integer
Dim c As String = ""
Dim opnd1 As Integer=0, opnd2 As Integer=0, dataValue As Integer =0
Dim index As Integer = 0
Me.operandStack = New Stack()
Do While index < Me.postFixString_Renamed.Length
c = Me.postFixString_Renamed.Substring(index, 1)
If isdigit(c) Then
Me.operandStack.Push(c)
Else
Try
opnd2 = Int32.Parse(Me.operandStack.Pop().ToString())
opnd1 = Int32.Parse(Me.operandStack.Pop().ToString())
If opnd1 = 0 AndAlso opnd2 = 0 Then
dataValue = 0
Else
dataValue = operate(c,opnd1, opnd2)
End If ' end of try
Catch
End Try
Me.operandStack.Push(dataValue)
End If 'end of isdigit(else)
index += 1
Loop ' end of while
Return dataValue
End Function ' 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.
NOTE: THIS ARTICLE IS CONVERTED FROM C# TO VB.NET USING A CONVERSION TOOL. ORIGINAL ARTICLE CAN BE FOUND ON C# CORNER (WWW.C-SHARPCORNER.COM).