Hi,

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. }


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. At character 19 i.e. at ‘*’ 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 = (

Statck = /((

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

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


Zulfi.

 

The 3rd rule is ambiguous. It says to do something UNTIL a left paren is encountered, but it doesn't say what to do WHEN a left paren is encountered.

 

Hi,
It says:
POP and output tokens until one of lower priority than t is encountered or a left parentheses is encountered.
You mean:
"POP and output tokens" is associated with "one of lower priority than t is encountered " i.e operator and not with left parentheses
i.e "POP and output tokens" is not associated with left parentheses
In another algorithm i found:
if entered character is Opening bracket "Push '(' onto stack

Can you show me a better algorithm for it?

Zulfi.

 

Hi,
i think there is a problem with this also:
<

If the token is an operator, *, /, +, or -, push it on the opstack. However, first remove any operators already on the opstack that have higher or equal precedence and append them to the output list.

>
For example, again considering the expression:
(4+8)*(6-5)/((3-2)*(2+2))
At character # 8 i.e. 6,
Stack: *(
Output: 4 8 + 6
Now at character 9 i.e. -,
Stack: (
Output: 4 8 + 6 *

which is wrong. It should be modified as:
If the token is an operator, *, /, +, or -, push it on the opstack. However, first remove any operators already on the opstack that occur before left parentheses and have higher or equal precedence and append them to the output list.

This would give us:
Character : -
Stack: *(-
Output: 4 8 + 6
Which is correct.
Kindly guide me is my logic correct.
Zulfi.

 

First you need to define the semantics of the infix notation being used.

For instance, if operators are left-associative you need different rules than if they are right associative. Also, if you have any unary operators then you have to be sure you deal with them. For instance,

6 * -3

has a unary operator, the minus sign, that has to be dealt with.

You also need to clarify what your "tokens" are. In most expression evaluators you first scan the string and tokenize it so that 234 is seen as a single token.

As best I can tell, you are restricting your expressions to the four arithmetic operators and the operands to single digit nonnegative integers. Is that correct?

A problem with the algorithm as you've described it (at least based on a quick mental review) is the notion of "until one of lower priority than t" is encountered. The problem is that after you read t you are continuing to scan the string and so you have moved past t. So how do you remember what t is in order to tell when you find one of lower priority? Keep in mind that this is inherently recursive. The algorithm needs to be written so that you can keep track of a single state variable and, based upon the next token in the input string and the current token on top of the stack; This can be done, but the algorithm you've given don't make it clear that they accomplish this. They seem more like they are intended for interpretation by a human being who is keeping track of "the big picture" in a way that is difficult for a computer program to do.

 

Hi,
i think there is a problem with this also:
<

If the token is an operator, *, /, +, or -, push it on the opstack. However, first remove any operators already on the opstack that have higher or equal precedence and append them to the output list.

>
For example, again considering the expression:
(4+8)*(6-5)/((3-2)*(2+2))
At character # 8 i.e. 6,
Stack: *(
Output: 4 8 + 6
Now at character 9 i.e. -,
Stack: (
Output: 4 8 + 6 *

which is wrong. It should be modified as:
If the token is an operator, *, /, +, or -, push it on the opstack. However, first remove any operators already on the opstack that occur before left parentheses and have higher or equal precedence and append them to the output list.

This would give us:
Character : -
Stack: *(-
Output: 4 8 + 6
Which is correct.
Kindly guide me is my logic correct.
Zulfi.

I think the original version is fine (or at least workable). Keep in mind that the parens are simply the highest precedence operator.

 

Hi,

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. }


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. At character 19 i.e. at ‘*’ 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 = (

Statck = /((

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

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


Zulfi.

Hi,

It looks like something is missing there or poorly described.
It also helps to create a precedence table (see below).

In any of these problems though it is best to show your entire work sheet. For example, for the problem:
(A+B)*C

you would show something like this:

[1]
char: (
stack: (
output:

[2]
char: A
stack: (
output: A

[3]
char: +
stack: (+
output: A

[4]
char: B
stack: (+
output: A B

[5]
char: )
stack:
output: A B +

Here you can see fully what took place. It's more work but it's also much more clear whether it is right or it is wrongly performed.

As noted however you should probably just look for a better algorithm. I remember way back the 'train track' algorithm if it's on the web somewhere.

A precedence table looks something like this:
p['+']=1;
p['-']=1;
p['*']=2;
p['/']=2;

but that's a very very short one with a very limited number of operation types.

Here's what i get:
output: 4 8 + 6 5 - * 3 2 - 2 2 + * /

and that looks right.

Here's what i found:

1. Create an empty stack called opstack for keeping operators. Create an empty list for output.
2. Convert the input infix string to a list by using the string method split.
3. Scan the token list from left to right.
   • If the token is an operand, append it to the end of the output list.
   • If the token is a left parenthesis, push it on the opstack.
   • If the token is a right parenthesis, pop the opstack until the corresponding left parenthesis is removed. Append each operator to the end of the output list.
   • If the token is an operator, *, /, +, or -, push it on the opstack. However, first remove any operators already on the opstack that have higher or equal precedence and append them to the output list.
4. When the input expression has been completely processed, check the opstack. Any operators still on the stack can be removed and appended to the end of the output list

Small note added: When popping operators in #3 above stop if a non operator is encountered.

Interesting coincidence...
On this same day (the 6th) back in December of 2007 i wrote the third version of an RPN program and for this problem it spit out:
48+65-*32-22+*/

which of course is the same as before with no spaces between chars. It was originally intended for alpha chars liike a, b, c, etc. If i remember right that became part of a huge calculator program some time later with the addition of some more rules for parsing functions and stuff like that.

 

Hi,
Congratulation on your achievement.Well done for your service to science & society.
<

A precedence table looks something like this:
p['+']=1;
p['-']=1;
p['*']=2;
p['/']=2;
>
I have a feeling that its against the BODMAS rule. According to BODMAS rule Division has precedence over multiplication.
am i right?
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 * according to BODMAS rule. But is the BODMAS rule followed in infix to postfix conversion?

Some body please guide me.
Zulfi.

 

Hi,
According to the algorithm in your post::
<

• If the token is an operator, *, /, +, or -, push it on the opstack. However, first remove any operators already on the opstack that have higher or equal precedence and append them to the output list.

>
Actually i was following this one:

<
If it is operator *+-/ then
If the stack is empty push it to the stack
If the stack is not empty then start a loop:
If the top of the stack has higher precedence
Then pop and append to output string
Else break
Push to the stack
>
It was not using the word "equal".
But again if we remove multiply (* symbol) from Stack then this means that it has a higher or equal precedence to division (/ symbol) which is contradictory to BODMAS. Kindly explain.
Zulfi.

 

Hi,
Congratulation on your achievement.Well done for your service to science & society.
<

A precedence table looks something like this:
p['+']=1;
p['-']=1;
p['*']=2;
p['/']=2;
>
I have a feeling that its against the BODMAS rule. According to BODMAS rule Division has precedence over multiplication.
am i right?
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 * according to BODMAS rule. But is the BODMAS rule followed in infix to postfix conversion?

Some body please guide me.
Zulfi.

Hi,

Interesting that you should talk about helping society as a whole because that is actually part of my goal. I also try to ignore borders such as place of origin or religion unless i must do so by the law of the lands although i may not agree with that law.


As to your dilemma, i believe you do not set a precedence for division over multiplication nor for addition over subtraction. In algebra, the order of operations is from left to right and division and multiplication are equal as are addition and subtraction.

This means to parse the following:
1+4/2*3

we go from left to right, and we find + first but there are div and mult to do first, so we do:
4/2

and get of course 2, then do:
2*3

and of course get 6, then we can do the addition which is 6+1=7.

Interestingly if we do 2*3 first and get 6 and then do 4/6 we get 2/3 and then 2/3+1=5/3 which is not right.

So it reads "multiplication and division before addition and subtraction" but there are only two levels of priority here not four.

Of course parens change all that;
1+4/(2*3)=1+4/6=5/3

which now is the right result because here we have parens which force us to do the 2*3 first.

It was not using the word "equal".
But again if we remove multiply (* symbol) from Stack then this means that it has a higher or equal precedence to division (/ symbol) which is contradictory to BODMAS. Kindly explain.
Zulfi.

If you did it right then the division symbol would be the last thing on the stack and you would see that everything else is done and so you would pop that division symbol last. The parens are what holds that on the stack in this case, so you cant pop it until last if you follow those rules i posted.

Let me just recap a little by saying again that for some of these problems you really have to jot down every little step you make so that other parties can follow your work. One little mistake and it does not work. If the question is about a work that is not shown, it can not be answered properly.

 

Hi,
Congratulation on your achievement.Well done for your service to science & society.
<

A precedence table looks something like this:
p['+']=1;
p['-']=1;
p['*']=2;
p['/']=2;
>
I have a feeling that its against the BODMAS rule. According to BODMAS rule Division has precedence over multiplication.
am i right?

No, you aren't. This is one of the reasons why I hate the use of teaching acronyms over teaching concepts -- people are forced to blindly (mis)interpret the acronym because they don't understand that it is just intended as a useful crutch to remember the concepts.

If you MUST use this acronym, you should remember it as

B-O-DM-AS or BO(DM)(AS)

Division and multiplication are of the same precedence and are left associative (i.e., done left to right). The same for addition and subtraction.

 

Hello again,

Here is the step by step decomposition..check it over and see if it looks right to you...
The first line of each step is the char encountered, the second line the stack, and the third line the output. Three underscores means there is nothing in there for that step ___.

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

==================================
(
(
___
==================================
4
(
4
==================================
+
(+
4
==================================
8
(+
48
==================================
)
___
48+
==================================
*
*
48+
==================================
(
*(
48+
==================================
6
*(
48+6
==================================
-
*(-
48+6
==================================
5
*(-
48+65
==================================
)
*
48+65-
==================================
/
/
48+65-*
==================================
(
/(
48+65-*
==================================
(
/((
48+65-*
==================================
3
/((
48+65-*3
==================================
-
/((-
48+65-*3
==================================
2
/((-
48+65-*32
==================================
)
/(
48+65-*32-
==================================
*
/(*
48+65-*32-
==================================
(
/(*(
48+65-*32-
==================================
2
/(*(
48+65-*32-2
==================================
+
/(*(+
48+65-*32-2
==================================
)
/(*
48+65-*32-22+
==================================
)
/
48+65-*32-22+*
==================================
___
___
48+65-*32-22+*/
==================================

 

Hi,
Thanks for removing my confusion about BODMAS and also for providing me a better alternate algorithm for this problem. Thanks for step by step solution. It would really help me in verification. I would also try to post my work.

Zulfi.

 

Hi,

You're welcome. I was also thinking of annotating each step after numbering each rule. That way we can see right then and there which rule caused the outcome that is shown in that step.