Algorithm to evaluate prefix expression?

Question

I have a prefix expression that only has the 4 binary operators(+,-,*,/) .A straight forward way to evaluate such an expression is to convert it to a postfix expression and then evaluate that expression. But I am looking for an algorithm that does this directly without converting it to any other expression ?

Are you sure your expression is prefix? Can you paste a few examples? Infix expressions are hard to evaluate, and are usually converted to postfix. — Amir Afghani, Feb 16 '13 at 17:54

rici · Accepted Answer · 2013-02-16T17:49:41.237

5

Simple recursion:

Evaluate(input):
  Read a token from input.
  If the token is a value:
    Return the value of the token
  If the token is a binary operator:
    Let first_argument = Evaluate(input)
    Let second_argument = Evaluate(input)
    Return apply(operator, first_argument, second_argument)

edited Feb 16 '13 at 17:49

answered Feb 16 '13 at 17:20

rici

234,347
28
237
341

score 0 · Answer 2 · answered Feb 16 '13 at 15:46

0

Use a stack. Place your vars and operators and start popping each stack, one for operators and the other for varaiablss (the number of pops depending on arity).

answered Feb 16 '13 at 15:46

Srikant Krishna

881
6
11

1

This is quite a vague answer. Do you have any sources ? – Feb 16 '13 at 15:50
2

It's called the pushdown automata model. – Srikant Krishna Feb 16 '13 at 15:52

Algorithm to evaluate prefix expression?

2 Answers2

Linked