is there any other way to convert infix expression to prefix besides using stacks algorithm..?? thanks..

: is there any other way to convert infix expression to prefix besides
: using stacks algorithm..?? thanks..

No, since precedence and parenthesis are recursive operations, you'll need recursion, and recursion can only be achieved with a stack like structure.

At every place you can use recursion, you can also use loops. In most of the cases it will give better performance, less risks and a more readable program.

: At every place you can use recursion, you can also use loops. In
: most of the cases it will give better performance, less risks and a
: more readable program.

True, true, but in this case data recursion is needed, which often goes best with code recursion. (i.e stacks are ugly)

But iteration is always faster, so it may be better anyway...

It is usually handy to break down ugly mathematical expressions and stuff like that into nodes of a double-linked list. From there you can start to calculate the expression, write the result to one of the "operand nodes" and then toss out the other, for example. I have written several such programs, equation solvers and similar, and I don't remember ever feeling the need to use recursion.

Anyway, it is hard to say that one algorithm is more suitable than another without a concrete example. "infix" could mean anything, really.

Hmm, how would you do hierarchies with a double linked list? Turn the expression into an post/prefix expression?

I think recursive parsers are really beautiful.

This is what is needed to parse binary operators and turn them into a prefix expression (what the OP wanted) (in psuedo code, written from head):

op(i){
  if i == 0
    advance()
    return token
  left = op(i-1)
  if next token has precedence level i
    advance()
    return token + left + op(i-1)
  return left
}

Advance is a function that advances the token pointer.
All that is needed is a tokeniser, which shouldn't be too hard to write.

It's easily extendable to parenthesis, unary operators and even functions.
(which I've done, and beyond)
Happy coding wishes
the one and only
Niklas Ulvinge aka IDK

Mathematicians think that recursion is beautiful, not programmers!

Programmers like things like speed, low memory consumption, safe programs without stack overflow and most important of all, readable code. Recursion is an evil leftover from old-school assembler programs back in the 80s when the storage size of the program was the resource-critical part and harddrives were measured in kilobytes, not gigabytes.


With a linked list, you would do something like this:

Parse through the expression and divide it into nodes. You need a method to determine where to start the evaluation of the expression, ie which node is the inner-most parenthesis. This could be done by for example adding a counter which you increase for every '(' and decrease for every ')', then copy down the counter to a priority variable inside every node, as you go through the expression.

After each evaluation, you store the result in one node and toss out the other, then decrease the node's priority by one, then check the node to the left and the node to the right, continue the evaluation on the node with highest counter, until you face null to both left and right.

Yeah it sounds fuzzy, but it will work. The disadvantage is the dynamic memory allocation, but then it is at least to prefer before recursion.

Ah, interesting. Must try it out!!!

Recursion isn't very bad when made by a good compiler.
It could be done with only 2 variables per call, which is allocated on the stack, which is much faster than memmory allocation on the heap.

It could never stack overflow, unless the number of tokens is bigger than the stack, which isn't likely.

Recursion takes as big space as iterative programming, and in this place takes as small memmory consumption too.

When data recursion is needed, recursive code is as good as iterative code, becouse instead of having a pointer that points to where the program is in the algorithm, it has code. It would be possible to construct a finite state machine if one went to the extreme.

Small code is always good, becouse now it makes it possible to put code in teh code cache.

Also, BNF is easely converted to a recursive algorithm.

The code I wrote could be written in (I admit, a wierd type of) BNF as

op[i] = op[i-1] + operator + op[i]
op[0] = operand

: Mathematicians think that recursion is beautiful, not programmers!
:
:

Only because mathematicians are to lazy to solve any recursive relations they find ;)
(And it often works well in proofs, certainly with induction :D)

Best Regards,
Richard

The way I see it... Well, it's all pretty blurry