Infix to Prefix conversion
Infix to Prefix conversion
================================================================================
- Infix expression: The expression of the form a operator b (a + b). When an operator is in-between every pair of operands.
- Prefix expression: The expression of the form operator a b (+ab). When an operator is prefix by every pair of operands.
- Algorithm:
- begin
- first reverse the infix expression
- replace the parenthesis as every "(" as ")" and every ")" as "("
- convert the modified expression to postfix by using infix to postfix algorithm
- reverse the final postfix string to get the resulted prefix expression
- begin
- first reverse the infix expression
- replace the parenthesis as every "(" as ")" and every ")" as "("
- convert the modified expression to postfix by using infix to postfix algorithm
- reverse the final postfix string to get the resulted prefix expression
- eg.
- (A + B ^ C) * D + E ^ S
- Solution:
- S ^ E + D * ) C ^ B + A (
- S ^ E + D * ( C ^ B + A )
Input
Stack
Output
S
S
^
S
E
S E
+
S E ^
D
S E ^ D
*
S E ^ D
(
S E ^ D
C
S E ^ D C
^
S E ^ D C
B
S E ^ D C B
+
S E ^ D C B ^
A
S E ^ D C B ^ A
)
S E ^ D C B ^ A +
S E ^ D C B ^ A + * +
- result = S E ^ D C B ^ A + * +
- reverse above expression to get final output
- + * + A ^ B C D ^ E S
Comments
Post a Comment