nongoto.cpp

经典c++程序的实现

#include <stdio.h>
#include <assert.h>
#include <iostream.h>

typedef struct elem {
  int rd, pn, pf, q;      // return address, n, f; q represate u1 and u2
} ELEM;

#include "..\include\book.h"
#include "..\include\astack.h"

class nonrec {
private:
  Stack S;

  void Enter(ELEM& x) {      // store data value on the stack
    S.push(x);
  }

public:
  nonrec(void) { }             // constuctor
  void replace2(int n, int& f);    // replace recursive
};

void nonrec::replace2(int n, int& f)  {

      ELEM x, tmp;

	  x.rd = 3;   x.pn = n;
	  Enter(x);      

      do  {
        while ((x = S.topValue()).pn >= 2)  {  // go down alone the left
          x.rd = 1;
          x.pn = (int)(x.pn/2);
          Enter(x);
        }

        x = S.pop();          // pf value when n <= 2
        x.pf = x.pn + 1;      // modify the pf as pn+1
        Enter(x);

        while ((x = S.topValue()).rd == 2) {   // go up from right
          tmp = S.pop();      // throw away the right node
          x = S.pop();
          x.pf = x.q * tmp.pf;   // compute the function value
          Enter(x);
        }

        if ((x = S.topValue()).rd == 1) {  // go up from left
          tmp = S.pop();        // throw away left node

          x = S.pop();          // record the returned value
          x.q = tmp.pf;
          Enter(x);

          tmp.rd = 2;          // go down to the right node
          tmp.pn = (int)(x.pn/4);
          Enter(tmp);
        }
      } while ((x = S.topValue()).rd != 3);

      x = S.pop();
      f = x.pf;
}

void main(void)  {
  nonrec rep;
  int f;

  rep.replace2(37, f);
  cout << "f(n) = " << f << endl;
}