Prefix(polish) notation - evaluation c++

Question

I am looking for code wchich parses prefix expressions using recursion. Primarily in C++, but it can bee in other language, i will translate. Thanks.

Answer 1

It's really easy to do yourself (you just need a stack for the operators (and sometimes/optionally its first term)).

But if you really don't want to do much work, here's a link:

prefix notation string to int conversion

If you need to use recursion, you basically use local variables in the function as individual elements in your stack.

Eg. pseudo-C++ code follows:

int naughtyglobalendindex = 0;
int parse(string str) {

  if (/* str starts off with an integer */) return the integer;

  char operator;
  operator = ?? // you will need to get the first op here. Maybe sscanf(str,"%c",&operator) or similar

  // get first argument
  int first = parse(/* str with 1st operator removed */);
  // get 2nd integer argument
  int second = parse(/* str - get substring from naughtyglobalendindex to end*/)

  // return first operator second <- this is pseudocode
  // in effect you want a switch clause
  switch (operator) {
    case '+': return first + second;
    case '-': return first - second; // and so on
  }
}

You can convert the pseudocode to actual C++, and if you want, fix the global naughtyglobalendindex variable if you want.