10-09-2016, 10:15 AM
1454309786-Group14.docx (Size: 288.45 KB / Downloads: 5)
1. Problem: Infix to postfix conversion using stack data structure
Problem Description:
Describe about the palindrome checking problem
Example:
Input: a+(b*c-(d/e^f)*g)*h output: abc*def^/g*-h*+
Solution using stack data structure:
A stack is used to hold operator and left bracket. Postfix expression is converted from left to right using operand from infix expression and operators which are removed from stack. left bracket is pushed on stack and a right bracket is added at the end of infix expression. This is continued until stack is empty.
Pseudo code:
(X denotes infix expression and Y denotes postfix expression)
1. Push “(“ onto STACK, and add “)” to the end of X.
2. Scan X from left to right and REPEAT Steps 3 to 6 for each element of X UNTIL the STACK is empty:
3. If an operand is encountered, add it to Y.
4. If a left parenthesis is encountered, push it into STACK.
5. If an operator is encountered, push it into STACK.
a) Repeatedly pop from STACK and add to Y each operator (on the top of STACK) which has the same precedence as or higher precedence than operator.
b) Add operator to STACK.
6. If a right parenthesis is encountered, then :
a) Repeatedly pop from the STACK and add to Y each operator (on the top of STACK) until a left parenthesis is encountered.
b) Remove the left parenthesis. [Do not add the left parenthesis to Y].
7. END.