Lecture 3:: Application of Stack

Expression Representation Techniques :
Expression is a collection of operators and operands that represents a specific value.
1.Infix Expression 2.Prefix Expression 3. Postfix Expression
Expression Example Note
Infix a + b Operator Between Operands
Prefix + a b Operator before Operands
Postfix a b + Operator after Operands

To evaluate an infix expression we need to consider Operators’ Priority and Associative property.
For example expression 3+5*4 evaluate to 32 i.e. (3+5)*4 or to 23 i.e. 3+(5*4).
Generally postfix expressions are free from Operator Precedence that s why they are preferred in Computer system. Computer System Uses Postfix form to represent expression.

Explanation the conversion in steps :
1. Read symbol from expression and it may be –
o Alphabet from A-Z or a-Z
o Numerical Digit from 0-9
o Operator
o Opening And Closing Braces ( , )
2. If Entered Character is Alphabet or Digit then Following Action Should be taken:
o Print Alphabet and Digit as Output
3. If Entered Character is Opening Bracket then Following Action Should be taken-
o Push ‘(‘ Onto Stack
o If any Operator Appears before ‘)’ then Push it onto Stack.
o If Corresponding ‘)’ bracket appears then Start Removing Elements [Pop] from Stack till ‘(‘ is removed.
4. If Entered Character is Operator then Following Action Should be taken::
o Check Whether There is any Operator Already present in Stack or not.
o If Stack is Empty then Push Operator Onto Stack.
o If Present then Check Whether Priority of Incoming Operator is greater than Priority of Topmost Stack Operator.
o If Priority of Incoming Operator is Greater than Push Incoming Operator Onto Stack.
o Else Pop (Operator that have high Priority or equal) From Stack and push incoming operator to stack, again go to Step 1.