Infix expression evaluation complexity

Question

What is the complexity of evaluating an infix expression having n operators?

Answer 1

It will be O(n) only.

Method 1 :

It takes O(n) time to convert a infix expression into the postfix expression and only one left to right scan is enough to compute the value of the expression which will take O(n) again.

So totally its O(n).

Reference :

1]  http://geeksquiz.com/stack-set-2-infix-to-postfix/ & http://geeksquiz.com/stack-set-4-evaluation-postfix-expression/

2] http://faculty.cs.niu.edu/~hutchins/csci241/eval.htm

---

Method 2 :

Alternative to method 1, you can also go for evaluation using two stacks, Operator stack & Operand stack.

Check this for more reference : http://stackoverflow.com/questions/13421424/how-to-evaluate-an-infix-expression-in-just-one-scan-using-stacks

Answer 2

O(n)

Comments

We do not use infix expression evaluation in compiler because its not linear.It should be more than O(n).Unlike postfix which  evaluates in O(n),in infix scanning the expression back and forth is required,to handle associativity and precedance.