Infix to Prefix

Hi

I need help to convert infix formula to prefix.. Has some body an implemented C or C++ code for that..It will be great favor ...
bye..

M.A.Malik

Why to prefix notation? I'm just curious what kind of application would need that.

Many years ago (24), I did do a program that implemented the "shunting algorithm" which converts infix to postfix (AKA "reverse Polish"). Though that was written in PL/I and the only copy of it that I have is a printout buried away somewhere.

Basically, the shunting algorithm (infix to postfix) works like this (I'm writing this from memory, BTW, so I apologize in advance for any mistakes):
1. You create a stack and an output string.
2. Then you read the infix string one token at a time; each token is either an identifier or an operator:
a. If the token is an identifier (eg, a variable or a constant), then you append it onto the end of the output string.
b. If the token is an operator, then you compare its precedence with the precedence of the operator on the top of the stack.
i. If the operator on the top of stack has lower precedence, then push the new operator onto the stack.
ii. Else, pop the operator from the top of stack and append it to the output string. Then push the new operator onto the stack.
otherwise
c. If the token is an open parenthesis, then push it onto the stack.
d. If the token is a close parenthesis, then pop and append the operators from the stack until the open parenthesis is popped. Discard both parentheses.

Google for "shunting algorithm" for a more detailed and better better description. You might also find reference to an algorithm for converting infix to prefix.

I think prefix or postfix can be more precisely used when one has to decide whether a formula is well formed or not . Formula I mean that carries all type of operators like +, -, /, *, binary or unary operator, exponent, logical operators, trignometeric functions, log functions, integrals and derivatives, quatitative operators, etc etc..
When we decide that a formula is well formed or not then we can decide about its complexity by having a binary tree. The parent of each subtree represents operators and sons are the operands...

I could not yet find an algorithm to convert infix form to prefix o postfix...

Anyone, who can help me in this matter...

M.A.Malik

Dijkstra's shunting algorithm should do the job. Use a search engine to find pages that describe it. You might even find some source code.

Hi,
Here is the algorithm to convert infix to postfix

looker=0
loop(looker <= length of string)
token = formula[looker]
if(token is left parenthesis)
pushstack(token)
else if(token is right parenthesis)
popstack(token)
loop( not left parenthesis)
concatenate token to postfix string
popstack(token)
else if (operator)
toptoken(tokenout)
loop(not emptystack() and priority(token)<= priority(tokenout))
popstack(token1)
concatenate token1 to postfix string
pushstack(token)

else(operand)
concatenate token to postfix string

loop(not emptystack())
popstack(token)
concatenate token to postfix string



HOPE YOU GET THIS PROBLEM SOLVED!

----------------------------------------------------------------