Precedence of operators in RPN

Question

While calculating postfix expression in C, if our token is an operator we have to place it the stack in such a way that it's has the highest priority.

My question is among the operators *, /, %, which has the highest priority.

Do we need to consider associativity as well ? Since all these operators have LEFT-TO-RIGHT associativity, will / get higher preference over * ?

Answer 1

Precedence usually only applies to infix notations. Postfix (and Prefix) notations are usually considered to explicitly specify which operands are associated with which operator. Precedence only comes into play when there is ambiguity in the parsing, which is not the case in postfix notation.

The precedence question that arises in an infix expression

4 * 5 + 3 / 12

simply doesn't exist after conversion to an RPN form

4 5 * 3 + 12 /

or a prefix form

(/ (+ (* 4 5) 3) 12)

.

There is some possibility for confusion when considering something like the Shunting-Yard Algorithm which can be used to generate an RPN representation from -- or directly evaluate -- an infix expression. It deals with operator precedence by deferring operators onto a secondary stack until a lower precedence operator forces it to be popped and evaluated (or output).

Answer 2

Operators *, /, % are same in precedence and there associativity is left to right. So an expression like:

a * b / c            /* both operators have same precedence  */

is same as:

(a * b) / c

Similarly an expression like:

a / b * c            /* both operators have same precedence  */

is same as:

( a / b ) * c

So even operators are same in precedence, but suppose if they appears in an expression(without parenthesis) then left most operator has higher precedence because of left to right associativity.

Note Conceptually we use parenthesis in an expression to overwrite precedence of operators, so although expression: a / b * c is same as: (a / b) * c but we can force to evaluate * first using ( ) by writing expression as a / ( b * c). What I means to say if you have confusion in operator precedence while writing code use parenthesis.

EDIT:

In POSTFIX and PREFIX form don't use parenthesis ( ). Precedence of operator are decided in order of there appearance in expression, So while evaluating an expression its not need to search next operation to perform - and so evaluation becomes fast.

While in INFIX expression precedence of operators can be overwritten by brackets ( ). Hence brackets are there in infix expression - and it need to search which operation to perform next e.g. a + b % d - and evaluation of expression is slow.
That is the reason conversion are useful in computer science.

So compiler first translates an infix expression into equivalent postfix form(using grammar rules) then generates target code to evaluate expression value. That is the reason why we study postfix and prefix form.

And according to precedence and associativity rules the following expression:

a * b / c            /* both operators have same precedence  */

will be translates into:

a b * c / 

And expression

a / b * c            /* both operators have same precedence  */

will be translated into

a b / c *