Doink

Hey guys, I need some help regarding prefix and postfix notations. I got myself confused like really bad. Correct me If i'm wrong...

So here are the questions...

infix > prefix notation

a) A * (B+C) - D

My answer is

= * A (+BC) - D

= *+A(BC) - D

= *+-A B C D

b) M / (E+Z) * N

= / M (E+Z) * N

= /+ (EZ) * m

= /+* MEZ


infix > postfix notation

a) - A / * E B M

= A / * E B M -

= A / E B M - *

= A E BM - * /


b) - + J K * L M

= + J K * L M -

= J K * L M - +

= J K L M - + *


I don't think what i did is right... >_>

Thanks....

laserlight

This does not really belong in C programming, so I have moved it to General Discussions.

A simple method here is to work from expressions that bind tightest ("inner expressions", to put it in another way). So you have say, two terms and an operator, and you shuffle them around until you get the desired notation, then you consider the result a new term, and so find the next term and operator to work with. For example:
A * (B+C) - D
A * (+ B C) - D
(* A + B C) - D
- * A + B C D

__________________
C + C++ Compiler: MinGW port of GCC
Build + Version Control System: SCons + Bazaar

Look up a C/C++ Reference and learn How To Ask Questions The Smart Way

Doink

Thanks for moving this topic.

but why did you put "-" before "*"? didn't you say you have to work from the inner expression first? So it should be like this = * - A + B C D

and also, what about the postfix? how do you begin to transform it?

CornedBee

Yes, and you insert at the front. So the later you handle an expression, the further to the front it appears.

Postfix is pretty much the same, except that you append at the back.

__________________
All the buzzt!
CornedBee

"There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
- Flon's Law

laserlight

A * (B+C) - D is actually (A * (B + C)) - D
So, once we have expressed (B + C) as (+ B C), we can express (A * (B + C)) in prefix notation as (* A + B C).

The infix equivalent of that expression would be: (A - (B + C)) * D

The idea is the same.

__________________
C + C++ Compiler: MinGW port of GCC
Build + Version Control System: SCons + Bazaar

Look up a C/C++ Reference and learn How To Ask Questions The Smart Way

Doink

Hey thanks again.

Now I just need to know the process to convert from prefix to postfix.

Do I need to convert it first to infix then to postfix?

CornedBee

Oh, no. Infix is the messiest of notations. The others are much easier to work with.

Prefix to postfix is quite easy with a recursive function. The function reads a token. If the token is a number, it writes it to the result. If it's an operator, it calls itself twice (for the two operands) and then writes the operator out.

__________________
All the buzzt!
CornedBee

"There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
- Flon's Law

Mario F.

Meanwhile, a visual trick to find the final expression is for you to first add all superfluous parenthesis following the usual order of evaluation rules for the expression at hand.

1. A / B + C * D
2. ( (A / B) + (C * D) )

Then move the operator within each parenthesis either to the left or right of both its operands, depending on the notation you want, while keeping the operator still inside its set of parenthesis.

3.prefix. ( + ( / A B) ( * C D) )
3.postfix. ( (A B / ) ( C D * ) + )

Then just remove the parenthesis.

4.prefix. + / A B * C D
4.postfix. A B / C D * +

__________________
Originally Posted by brewbuck:
Reimplementing a large system in another language to get a 25% performance boost is nonsense. It would be cheaper to just get a computer which is 25% faster.