Some Operations using Stacks!!!!
Infix To Postfix Conversion.
Well Consider the expression 1. A+B
The Postfix of the above expression will be AB+
Here the operator(+,/,*,-) comes after two operands.
Now before writing a program it is essential to know how we can convert a infix expression to post fix expression.
Here we will be using two arrays. One of them will be our stack and other will contain the post fix expression.
Step 1: Read/Scan the expression from left to right by scanning one character at a time.
Step 2: If you find '(' Symbol push it to the stack.
Step 3: If you find operator( may be A,B...Z) push it in the post fix expression array.
Step 4: If you find any operator (+,-,/,*) Note its precedence
/* Note : Precedence of / is greater than *
Precedence of * is greater than +
Precedence of + is greater than -
i.e. Precedence of />*>+>- */
If there is any operator in the stack, check the precedence of the scanned operator.
If the precedence of the scanned operator is less than or equal to the operator which is present in the stack than the operator present in the stack is removed and pushed into the post fix expression array.
If the precedence of the scanned operator is greater than the operator which is present in the stack than the scanned operator is also pushed into the stack.
Step 5: If the ')' symbol is found than the operator which are present between the previous '(' are removed and pushed in to the postfix expression array.
Example: Convert the following infix expression to post fix expression.
(A+B/C*(D-E))
Read/Scan Stack Final Post Fix Expression
1.( (
/* See step 2, since '(' symbol is found it is pushed in to the stack*/
2. A ( A
/* Since an operand is found it is pushed in to the post fix expression*/
3. + (+ A
/*Since an operator is found and no other operator is currently present in the stack so the operator is pushed into the stack*/
4.B (+ AB
/* Since an operand is found it is pushed in to the post fix expression*/
5./ (+/ AB
/*Since the precedence of / is greater than that of +, so / can be pushed in to the stack.*/
6 C (+/ ABC
/* Since an operand is found it is pushed in to the post fix expression*/
7. * (+* ABC/
/* Since the precedence of * is less than that of /, so / is removed from the stack and pushed in to the postfix expression and * is pushed in to the stack.*/
8. ( (+*( ABC/
/* See step 2, since '(' symbol is found it is pushed in to the stack*/
9. D (+*( ABC/D
/* Since an operand is found it is pushed in to the post fix expression*/
10. - (+*(- ABC/D
/*Since an operator is found it is pushed in to the stack*/
11. E (+*(- ABC/DE
/* Since an operand is found it is pushed in to the post fix expression*/
12.) (+* ABC/DE-
/* Since a '(' is found the operator which was present between the ( and ) symbol was removed from the stack and pushed in to the post fix expression.*/
13. ) ABC/DE-*+
/* Since again ')' is found the operators which were present between the ( and ) symbol were removed and pushed in to the post fix expression in reverse order and the final post fix expression is obtained.*/
Infix: (A+B/C*(D-E))
Final Post Fix Expression : ABC/DE-*+
Next Blog Post will contain the Program code for Infix to Post Fix conversion.
========================= About The Blogger=============================
The Blogger is Rishi Jain, who is perusing Engineering in Computer Science at Samrat Ashok Technological Institute, Vidisha. The Blogger has a keen interest in programming and would like to accept challenges to code a program. The Blogger has prior knowledge of JAVA Basics and had scored 100/100 in Computer Science Java Programming in ICSE 10th Board and 99/100 in Computer Science Java Programming in ISC 12th Board Examinations.
No comments:
Post a Comment