## C and C++

Moderators: None (Apply to moderate this forum)
Number of threads: 28695
Number of posts: 94715

This Forum Only

infix to prefix need help. Posted by aldrin_gapuz on 2 Oct 2007 at 8:14 AM
is there any other way to convert infix expression to prefix besides using stacks algorithm..?? thanks..
Re: infix to prefix need help. Posted by IDK on 2 Oct 2007 at 9:41 AM
: 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.
Re: infix to prefix need help. Posted by Lundin on 2 Oct 2007 at 11:22 PM
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.
Re: infix to prefix need help. Posted by IDK on 3 Oct 2007 at 4:55 AM
: 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...
Re: infix to prefix need help. Posted by Lundin on 3 Oct 2007 at 7:18 AM
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.
Re: infix to prefix need help. Posted by IDK on 3 Oct 2007 at 12:18 PM
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
Re: infix to prefix need help. Posted by Lundin on 3 Oct 2007 at 11:51 PM
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.
Re: infix to prefix need help. Posted by IDK on 4 Oct 2007 at 2:05 AM
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
```

Re: infix to prefix need help. Posted by BitByBit_Thor on 4 Oct 2007 at 6:46 AM
: 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

## Recent Jobs

Official Programmer's Heaven Blogs
Web Hosting | Browser and Social Games | Gadgets

Popular resources on Programmersheaven.com
Assembly | Basic | C | C# | C++ | Delphi | Flash | Java | JavaScript | Pascal | Perl | PHP | Python | Ruby | Visual Basic
© Copyright 2011 Programmersheaven.com - All rights reserved.
Reproduction in whole or in part, in any form or medium without express written permission is prohibited.
Violators of this policy may be subject to legal action. Please read our Terms Of Use and Privacy Statement for more information.
Operated by CommunityHeaven, a BootstrapLabs company.