1

I'm reading Sedgewick's book on algorithms in C and I'm looking for an algorithm to evaluate postfix expressions (addition and multiplication only) without using a stack. I tried to implement one but I always get nowhere.

I have a simple C implementation for prefix evaluation 

int eval()
{
  int x = 0;

  while (a[i] == ' ')
    i++;
  if (a[i] == '+')
    {
      i++;
      return eval() + eval();
    }
  if (a[i] == '*')
    {
      i++;
      return eval() * eval();
    }
  while ( (a[i] >= '0') && (a[i] <= '9'))
    x = 10*x + (a[i++]-'0');
  return x;
 }

and I was wondering if it's possible to do something as elegant as this but for postfix evaluation.

caisah
  • 113
  • 1
  • 5
  • Any reason why you *don't* want to use a stack for postfix? Part of the reason for postfix is the efficient use of a stack. –  Dec 03 '13 at 17:33
  • This is how the exercise is being formulated. I guess I can use the stack as long as I write a recursive function. It's a chapter about recursion and I think the author intends for the reader to get familiarized with recursion. – caisah Dec 03 '13 at 20:30
  • 2
    Have you tried asking your instructor then? They've got a better idea of the answer they are trying to extract from the exercise than we do. One of the 'problems' with asking about homework on P.SE is that we tend to be a bit more 'pragmatic' in our solutions much of the time. You want elegance? Use a stack. Reinvesting the wheel and doing things the hard way is often antithetical to the mindset of the non-academic programmer. –  Dec 03 '13 at 20:34
  • I don't have an instructor I'm learning by myself and this is why I asked here. Anyway I realized this kind of coding is not meant for production, it has academic purpose only. Anyways, I was curious if some more experience programmer could show me a different approach before squeezing my brains out. – caisah Dec 03 '13 at 20:44

5 Answers5

5

I wouldn't exactly call using a global variable as a string index counter 'elegant', but in a nutshell: No, you can't, because you have no idea how to combine the various numbers you find until you get to the operators. Until you do, you have to store them somewhere - and to get the right result, whatever your storage strategy is will ultimately boil down to stack semantics.

Kilian Foth
  • 107,706
  • 45
  • 295
  • 310
  • 1
    I disagree. It is possible, however it would require that the returning recursive method both returns the calculated value as well as the index to read the next term. – Neil Dec 03 '13 at 15:31
  • 2
    It's possible to do without using a *user-defined* stack data structure, but you're still storing the operands on the run-time stack of your programming environment. Obviously, this is usually better than hacking together your own stack structure, but to me, that's still "using a stack". – Kilian Foth Dec 03 '13 at 15:34
  • I would contend that for evaluating a postfix expression, using recursion vs using a stack (either user defined or existing library) - the recursion would be less elegant - it boils down to if you are storing numbers on the stack or operands in recursion. I would advocate that the simplicity and of the number stack would be easier to comprehend and more elegant than recursion. Though, thats certainly opinion. –  Dec 03 '13 at 16:33
  • 1
    Certainly using recursion to do this sort of defeats the purpose of using post-fix in the first place since it is meant to be easily handled with a simple stack, however recursion itself has a call stack with local variables which can have the same effect. It would simply be far less efficient. – Neil Dec 03 '13 at 16:35
  • @MichaelT Thanks for the comment. This is exactly what I was referring to, when I used the word _elegant_ in the question. @ Neil You are suggesting some kind of tail recursion, right? – caisah Dec 03 '13 at 16:50
  • @caisah Since the problem with recursion is that it eats up a variable number of items, if you're using a string, you must then know how much of it has been calculated by the recursive call, so it must return both the value and index. My point was simply to correct the fact that it isn't impossible, just awkward and inefficient. – Neil Dec 05 '13 at 10:22
1

you pass the top 2 in the stack as parameter at each point, this way when you get to an operator you go up the stack when you see a value you go down the stack and when you get back you try again:

here is the magic:

eval(int x1, int x2)
{
 do{
   int x = 0;
   while (a[i] == ' ')
     i++;
   if (a[i] == '+')
    {
      i++;
      return x2+x1;// go up the stack with the resulting value
    }
   if (a[i] == '*')
    {
      i++;
      return x1*x2;
    }
   while ( (a[i] >= '0') && (a[i] <= '9'))
      x = 10*x + (a[i++]-'0');
   x2 = eval(x2, xt); // replace the old top with the result and try again
 }while(true);
}

you just need to add 2 functions to handle the errors when operators appear as the first 2 terms:

eval()
{
 int x = 0;
  while (a[i] == ' ')
    i++;
 if (a[i] == '+')
    {
      i++;
      return ERROR;
    }
  if (a[i] == '*')
    {
      i++;
      return ERROR;
    }
  while ( (a[i] >= '0') && (a[i] <= '9'))
    x = 10*x + (a[i++]-'0');
  return eval(x);
}

eval(int x1)
{
 int x = 0;
  while (a[i] == ' ')
    i++;
 if (a[i] == '+')
    {
      i++;
      return ERROR;
    }
  if (a[i] == '*')
    {
      i++;
      return ERROR;
    }
  while ( (a[i] >= '0') && (a[i] <= '9'))
    x = 10*x + (a[i++]-'0');
  return eval(x1, x);
}
ratchet freak
  • 25,706
  • 2
  • 62
  • 97
1

and I was wondering if it's possible to do something as elegant as this but for postfix evaluation.

Postfix notation isn't meant to be processed with a call stack or recursion or really anything of that nature. Its designed for nice, tight implementations that just have a simple loop and a stack next to it. These fall into the realm of stack machines and are often found in embedded systems because of their simplicity. You find things like forth, postscript and the jvm as very successful stack machines (see Wikipedia - Category stack based virtual machines) along with venerable HP rpn calculator.

The elegance of postfix can be seen in the simple loop:

while not end of file
    read into var
    if var is not operand
        push var
    else if var is '+'
        pop into v1
        pop into v2
        push v1 + v2
    else if var is '*'
        pop into v1
        pop info v2
        push v1 * v2

And thus you go through and implement all the operands and you're done. dc has 27 operands (things like print (pop and print) P, print (just print) p, print the stack f, clear the stack c, etc...). You can read them at dc.1 man page. I will admit there are some more elegant structures for implementing the operands rather than a huge if else if cascade depending on the language... but you get the idea.

The elegance of the system is its simplicity. You don't have to worry about stack frames, calling conventions, and the like when implementing it. You've got a stack and a variable or two.

0

I would consider the problem as:

  • a parsing problem. read some good compiler text book like the Dragon book. So parse your expression into some Abstract Syntax Tree sitting in the virtual address space of your process.

  • then, evaluate that AST (in some environment).

The above approach fits for any expression-like language (not only postfix, but also prefix, or infix, etc...).

Alternatively, a postfix expression can be considered as some bytecode for a stack automaton (or pushdown automaton) based interpreter.

Basile Starynkevitch
  • 32,434
  • 6
  • 84
  • 125
-1

Definition: postfix = identifier | <postfix> <postfix> <operator>

To evaluate a postfix expression, we scan it from the last character to the first one in the expression, then perform the operation indicated by the last character on the two operands on the left, evaluated recursively.

char *a;
int i = strlen(a)-1;
int eval()
{
  int x = 0;
  int factor = 1;
  while (a[i] == ' ') i--;
  if (a[i] == '+')
  { i--;  return eval() + eval(); }
  if (a[i] == '*')
  { i--; return eval() * eval(); }
  while ('0' <= a[i] && a[i] <= '9')
  { x = x + (a[i--] - '0') * factor;  factor *= 10; }
  return x;
}
RaidenF
  • 1,499
  • 1
  • 13
  • 17
zzz
  • 1
  • 1