Infix to Postfix

[Ceset]

Hi all.

I am trying to write a console program that is based on python. It takes an infix expression and converts it to postfix.

This is a c++ forum and why i am asking it here, right?

Well, it is a shame that my native language is not english and sometimes i can't understand technical expressions very well. Which is where i am having trouble.

http://scriptasylum.com/tutorials/infix_postfix/algorithms/infix-postfix/
In the upper link, it tells how to convert infix to postfix. But i am having trouble understanding this exact sentence "If the scanned character is an Operand and the stack is not empty, compare the precedence of the character with the element on top of the stack (topStack)". Can someone explain me? Especially the "precedence" part.

Sorry for asking such a shameful question. But i have noone near me who knows math or english better than me. And i have been struggling for 3 hours already. It has a visual example even but... :(

Thanks in advance

[Duthomhas]

There's nothing shameful about not knowing another language.

Google Translate is often particularly useful:
https://translate.google.com/translate?sl=es&tl=tr&js=y&prev=_t&hl=en&ie=UTF-8&u=http%3A%2F%2Fscriptasylum.com%2Ftutorials%2Finfix_postfix%2Falgorithms%2Finfix-postfix%2F&edit-text=&act=url
(I'm not sure I got the URL right on that one. I hope it works for you.)

An "operand" is something that gets "operated on" -- in other words, it is a number or a variable name.

    3 + a

The operator is +. The operands are 3 and a.

"Precedence" is 'evaluation order'. For example, multiplication has a higher precedence than addition, because given the choice, multiplications happen first.

    3 + 4 * 5

Which comes first? 3 + 4 or 4 * 5. Since multiplication comes first (it has a higher precedence), the answer is 4 * 5.

Hope this helps.

[giblit]

The basic algorithm is this:


Operands - Things that will be operated on.
Operator - The operation to operate on the operands.

Example 1: 4 / 5 - operands: 4 and 5, operator: /
Example 2: a * b - operands: a and b, operator: *

Operation precedence (priority): * / % + - (for basic infix to postfix)
* = 1
/ = 1
% = 1
+ = 2
- = 2


I would look at the example that they provide.

Example :

Let us see how the above algorithm will be imlemented using an example.

Infix String : a+b*c-d

Initially the Stack is empty and our Postfix string has no characters. Now, the first character scanned is 'a'. 'a' is added to the Postfix string. The next character scanned is '+'. It being an operator, it is pushed to the stack.


Stack
Postfix String

Next character scanned is 'b' which will be placed in the Postfix string. Next character is '*' which is an operator. Now, the top element of the stack is '+' which has lower precedence than '*', so '*' will be pushed to the stack.


Stack
Postfix String

The next character is 'c' which is placed in the Postfix string. Next character scanned is '-'. The topmost character in the stack is '*' which has a higher precedence than '-'. Thus '*' will be popped out from the stack and added to the Postfix string. Even now the stack is not empty. Now the topmost element of the stack is '+' which has equal priority to '-'. So pop the '+' from the stack and add it to the Postfix string. The '-' will be pushed to the stack.


Stack
Postfix String

Next character is 'd' which is added to Postfix string. Now all characters have been scanned so we must pop the remaining elements from the stack and add it to the Postfix string. At this stage we have only a '-' in the stack. It is popped out and added to the Postfix string. So, after all characters are scanned, this is how the stack and Postfix string will be :


Stack
Postfix String

End result :
Infix String : a+b*c-d
Postfix String : abc*+d-

Edit: I guess I took a really long time to finish typing my message. Guess that is why you probably shouldn't eat while thinking about what to say.

[ne555]

If the scanned character is an Operand and the stack is not empty, compare the precedence of the character with the element on top

I think that there is an error there. It should say
If the scanned character is an Operator

[Ceset]

Sorry, everyone. I had an internet connection problem and was fighting with it for the last few days. Could'nt take a look at answers.

@Duoas google translate is not that useful in my native language :( . But your answer explains it very nice.

@giblit i looked at example but it couldn't help me undestand the exact sentence i wrote. :(

@ne555 if what you said is true, i am very angry. It cost me 5 hours at total.

Now i am going to finish my code.