Stack Application

 

Stack Application

1.   Balancing parenthesis.

2.   Infix to postfix conversion

3.   Evaluating postfix expression

4.   Recursive function calls

 

Balancing Parenthesis

 

Steps to Check for Balanced Parentheses using a Stack

1. Initialization:

• Create an empty stack.

2. Traversal:

• Iterate through the given expression character by character.

3. Processing Characters:

• Opening Parenthesis:
• Push the opening parenthesis onto the stack.
• Closing Parenthesis:
• If the stack is empty, the expression is unbalanced.
• Else – Pop the top element from the stack. If the popped element is not the corresponding opening parenthesis, the expression is unbalanced.

4. Final Check:

• After processing all characters, if the stack is empty, the expression is balanced.
• If the stack is not empty, the expression is unbalanced.

 

Infix to postfix conversion

 

Steps to Convert Infix to Postfix Expression Using a Stack

1.   Initialize a Stack: Create an empty stack to store operators.

2.   Scan the Infix Expression: Read the infix expression from left to right, character by character. (Ignore / skip blank spaces)

3.   Process Each Character:

o  Operand: If the character is an operand (a number or variable), append it directly to the postfix expression.

o  Operator: If the character is an operator:

§  If the precedence of the top operator is lower than the precedence of the current operator, push the operator on to the stack.

§  If the precedence of the top operator is greater than or equal to the precedence of the current operator, Pop the operator from the stack and append it to the postfix expression. Repeat this until the top operator has lesser precedence than the current operator or the stack becomes empty. Finally Push the current operator onto the stack.

o  Left Parenthesis: Push the left parenthesis onto the stack.

o  Right Parenthesis: Pop operators from the stack and append them to the postfix expression until a left parenthesis is encountered. Pop and discard the left parenthesis. Discard the right parenthesis also.  

4.   Empty the Stack: After processing the entire infix expression, pop any remaining operators from the stack and append them to the postfix expression.

 

Evaluate a postfix expression:

1. Initialize a Stack: Create an empty stack to store operands.
2. Scan the Expression: Iterate through the expression, character by character.
• If the character is an operand: Push it onto the stack.
• If the character is an operator:
• Pop the top two operands from the stack.  
• Perform the operation on the two operands.
• Push the result back onto the stack.
3. Final Result:
• After processing the entire expression, the final result will be the only element left on the stack.