Conceptual issue occurred while converting infix notation to postfix notation

Question

How can I realize/understand what is the preferential order/precedence of operators while converting infix notation to postfix notation : " * ", " / ", " + ", " - ", " ^ ", " ) ", " ( ".

I understand that one can just look at an algorithm for this and solve this but I don't want to do that. What should be my thought process?

Answer 1

If parentheses are balanced properly you can always find a parenthesis-free subexpression, which reduces the problem to that case.

Now just ask yourself, according to precedence rules, which operation in such an expression should be performed first?

Answer 2

Operator precedence is a convention and property of a formal infix language to indicate which operations should evaluate first. A higher precedence operation means that it should operate before lower precedence operations.

Grouping parentheses are not part of the operator precedence. (Note that other kinds of parentheses such as function call parentheses may be however I am assuming you do not refer to those here) They are used to explicitly indicate the order of operations. Parentheses are only useful to indicate an order of operations in infix notation. The purpose of the operator precedence convention in a given language is to avoid using parentheses in most case. So, for example, if I want to multiply 4 by 5 and then add 7 to the result, I can write:

4*5+7

This is valid under normal arithmetic operator precedence rules because multiplication ('*') has higher precedence than addition ('+'). But if I want to add 3 and 4 and then multiply this result by 8, I need to write:

(3+4)*8

In this case I want the order of operations to be different than the normal order of "higher precedence operations first." In other words, parenthesis are only necessary when we are using infix notation and want operations to execute in an order other than precedence-order.

In standard arithmetic, exponentiation ("^") has highest precedence. Next is multiplication and division (equal precedence) and finally addition and subtraction. Therefore, an infix expression written using these operators without parenthesis will evaluate all exponentiation first, then all multiplications and divisions (in left to right order) and finally all additions and subtractions, again in left to right order.

If you want to infer the operator precedence of an unknown language, you would need to look at the places where parentheses are and are not used. Since it is valid to use parentheses everywhere even when unnecessary, this is only a heuristic. For the examples above, I can write:

((4*5)+7)

And this gives no hint about operator precedence. It is because every binary operator in this case has parentheses, and therefore at least one of the two sets is redundant assuming the precedence of addition and multiplication are not the same.

Similarly, looking at the next example:

(3+4)*8

since parentheses were used around the addition but not the multiplication, we can infer that probably in this language addition has lower precedence than multiplication. Otherwise, the parenthesis would be redundant. So look for the pattern where parentheses are and are not used to try to figure out operator precedence in unknown languages. It is more common to assume a certain precedence level based on the formal specification of the language under consideration. Most formal languages have an operator precedence chart for the infix form to avoid this ambiguity.

We never need parentheses in prefix or postfix languages because the order of terms and operators already makes the order of evaluation explicit. Therefore this issue is really an infix-language-specific problem.