Problem with Conversion from Infix to Postfix Notation

[zak100]

Homework Statement

I am trying to convert following from infix to post fix:

(4+8)*(6-5)/((3-2)*(2+2))

I am facing problem at character 20 which is a ‘(‘ i.e. opening bracket.

Homework Equations

There is no eq but the algorihm is given below:
I got following algorithm from internet.

1. if (t is an operand) output t.

2. else if (t is a right parentheses){ POP and output tokens until a left parentheses is popped(but do not output) }

3. else { POP and output tokens until one of lower priority than t is encountered or a left parentheses is encountered. or the stack is empty. PUSH t. }

The Attempt at a Solution

I am facing problem at character 20 which is a ‘(‘ i.e. opening bracket. At character 19 i.e. at '*' i.e. (asterisk) I have following status:

Character = *

Stack = /(*

Output = 4 8 + 6 5 - * 3 2 –

At character 20 i.e. ( , as per above algorithm, I would come to step 3. so I am popping tokens & I have following status after character 20:

Character = (

Stack = /((

Output = 4 8 + 6 5 - * 3 2 – *

But the above is wrong. Some body please guide me what is my mistake?Zulfi.

 

[jedishrfu]

Here is a better set of rules:

http://csis.pace.edu/~wolf/CS122/infix-postfix.htm

Weren't you supposed to push the * onto the stack so it would /(* and then it would be /(*( then you'd output the 2 then the stack would be /(*(+ ...

 

[zak100]

Hi,
I have got a problem with precedence. According to BODMAS rule, division has precedence over multiplication but the infix to posfix conversion algorithm is working opposite to this rule & giving precedence to division over multiplication. For instance in the expression:
(4+8)*(6-5)/((3-2)*(2+2))

At character# 12 which is /, we have following situation:
Character: /
Stack: *
Output: 4 8 + 6 5 -
I have seen that many solutions show:
Stack: /
Output: 4 8 + 6 5 - *

I think this is not right because / has more precedence over *.

Some body please guide me.
Zulfi.

 

[berkeman]

According to BODMAS rule, division has precedence over multiplication but the infix to posfix conversion algorithm is working opposite to this rule & giving precedence to division over multiplication

From Wikipedia:
https://en.wikipedia.org/wiki/Order_of_operations

The order of operations used throughout mathematics, science, technology and many computer programming languages is expressed here:[3]

exponents[1] and roots
multiplication[1] and division[1]
addition[1] and subtraction[1]

I'm no expert on the Order of Precedence, but multiplication and division have the same precedence, I believe. So in your equation, without more brackets in the equation, the usual factor that decides whether * or / is done first is left-to-right. So in your equation, the * would be applied after seeing the / character and before the terms to the right of the / character are parsed.

 

[zak100]

Hi,
Thanks for removing my confusion. I got the same answer from another forum & they removed my BODMAS confusion also.
https://forum.allaboutcircuits.com/threads/problem-with-conversion-from-infix-to-postfix-notation.132914/

Thanks all for providing me help and related algorithm. This problem is solved now.

Zulfi.