Thread: Reverse Polish Notation???

Well I do have a text with a case study on Polish Notation (Data Structures and Program Design in C, ISBN 013288366), but to type out the code would take ages. It doesn't cover reverse Polish Notation however, but it may get things started for you.

hth

edit - you may also want to look at this http://www.naveen.net/calculator/ - it's in javascript, but it might be worth a look

Gimme a sec I'll type it out.

Code:

/* InfixtoPostfix - translate from infix to postfix form
Pre: The input is a valid expression in infix form.
Post: The output is the input expression converted into postfix expression. */

void InfixtoPostfix(Expression expr, Expression postfix)
{
	Stack stack;
	StackEntry topentry;
	Token token, tmp;
	KindType type;

	CreateStack(&stack);
	do {
		GetToken(token, expr);
		switch (type = Kind(token)){

		case OPERAND:
			PutToken(token, postfix);
			break;

		case LEFTPAREN:
			Push(token, &stack);
			break;

		case RIGHTPAREN:
			for (Pop(token, &stack); Kind(token) != LEFTPAREN; Pop(token, &stack))
				PutToken(token, postfix);
			break;

		case UNARYOP:	/* Treat both kinds together */

		case BINARYOP:
			do {
				if (StackEmpty(&stack))
					break;
				else {
					StackTop(&topentry, &stack);
					if(Kind(topentry) == LEFTPAREN)
						break;
					else if (Priority(topentry) < Priority(token))
						break;
						else if (Priority(topentry) == Priority(token)
							&& Priority(token) == MAXPRIORITY)
							break;

						else {
							Pop(tmp, &stack);
							PutToken(tmp, postfix);
						}
				}
			}while (1);
			Push(token, &stack);
			break;

		case ENDEXPR:
			while(!StackEmpty(&stack)) {
				Pop(token, &stack);
				PutToken(token, postfix);
			}
			break;

		}
	}while (type != ENDEXPTR);
}

From the text...

"Since, in postfix form, all operators come after their operands, the task of translation from infix to postfix form amounts to moving operators so that they come after their operands instead of before or between them."

Delay each operator until its right-hand operand has been translated. Pass each simple operand through to the output without delay

Examples -

infix form: x + y @ x x + y + z

postfix form: x y + x @ x y z +