Vivekanand Vellanki
2

Actually, all 3 are equally easy for a computer - postfix, infix and prefix. The part that is challenging for a computer is parsing an expression and figuring out the order in which things need to be evaluated. This is the process of parsing and tokenising the expression to build what is usually called an expression-tree.


Lets take an example of an expression and see why it is hard for computers to parse an expression.


10 + 15 / 4 * 10 - -4 % 7 + 2; where % is the modulo operator.


To be able to figure out what needs to be done, the computer needs to figure out the following:

  1. Understand BODMAS so that it knows the evaluation order, especially when there are no parenthesis like in the above example
  2. Understand the number of operands operators have; + has 2 operands, / has 2 operands, etc.
  3. Understand exceptions to the above rule of number of operands; - -4 where the 1st - is a binary operator and the 2nd - is a unary operator. The same applies to the + operator too
  4. Handle other ambiguity. For e.g., BODMAS doesn't mention the evaluation order for operators like %. Is a + b + c % d, (a + b + c) % d? or a + (b + c) % d? or something else?


For input given in the above form, the task of parsing the expression and figuring out the evaluation order is challenging for a computer - it is challenging even for a human.


If the input expression is given in the form of a postfix expression, it is easy for the computer because the computer doesn't have to deal with most of the issues highlighted above.


If the input were given as:

(((10 + ((15 / 4) * 10)) - (-4)) % 7) + 2; this would be easy enough for a computer since the parenthesis take care of the order of evaluation. The computer still has to build a tree.


The post-fix form:

10, 15, 4, /, 10, *, +, -4, -, 7, %, 2, + is hard for a human to read, but it is easy for a computer to understand and evaluated. It doesn't have to worry about parsing, order of evaluation, etc.


For the above, the computer would do the following in a loop as it reads input:

  • If it read an operand and push to a stack
  • If it read an operator; pop enough arguments from the stack; apply the operator; and push the result back into the stack


Try the above on the given post-fix to see how it is to evaluate the expression.