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
64.3k questions
77.9k answers
244k comments
80.0k users