It would be greatly appreciated if someone would take a moment to demonstrate a D templatized, linked list version of a pushdown stack and its use in evaluating postfix- and infix-expressions ie. "5 9 8 + 4 6 * * 7 + *" or "5 * { [ ( 9 + 8 ) * ( 4 * 6 ) ] + 7 }"

Thanks,
Andrew

"Andrew Edwards" <edwardsac@spamfreeusa.com> escribió en el mensaje
news:bcr3ho$1q0a$1@digitaldaemon.com...
| It would be greatly appreciated if someone would take a moment to
| demonstrate a D templatized, linked list version of a pushdown stack and
its
| use in evaluating postfix- and infix-expressions ie. "5 9 8 + 4 6 * * 7 +
*"
| or "5 * { [ ( 9 + 8 ) * ( 4 * 6 ) ] + 7 }"
|
| Thanks,
| Andrew
|
|

If it's any good, I did something similar a long time ago, but with no templates, with a binary tree, and for infix expressions.

————————————————————————— Carlos Santander


---
Outgoing mail is certified Virus Free.
Checked by AVG anti-virus system (http://www.grisoft.com).
Version: 6.0.490 / Virus Database: 289 - Release Date: 2003-06-16

"Carlos Santander B." <carlos8294@msn.com> wrote in message news:bcr9nu$1v8m$1@digitaldaemon.com...
>
> If it's any good, I did something similar a long time ago, but with no templates, with a binary tree, and for infix expressions.
>
> -------------------------
> Carlos Santander

Carlos! I would be a fool to turn down an opportunity to learn another way of accomplishing the task! Thank you very much for this opportunity to expand my knowledge. The intent however is to gain comfort in the proper use of D templates and classes in a context I understand. (i.e. pushdown stack && linked lists)

"Andrew Edwards" <edwardsac@spamfreeusa.com> escribió en el mensaje
news:bcs41b$2lq4$1@digitaldaemon.com...
|
| Carlos! I would be a fool to turn down an opportunity to learn another way
| of accomplishing the task! Thank you very much for this opportunity to
| expand my knowledge. The intent however is to gain comfort in the proper
use
| of D templates and classes in a context I understand. (i.e. pushdown stack
| && linked lists)
|

No problem

————————————————————————— Carlos Santander


---
Outgoing mail is certified Virus Free.
Checked by AVG anti-virus system (http://www.grisoft.com).
Version: 6.0.490 / Virus Database: 289 - Release Date: 2003-06-16

What follows is a simple use of the stack ADT. I have two questions: 1) How do I make the Stack class a template? 2) Why is it possible to access the variable "top" from within main?

Thanks,
Andrew

//import stream;
alias int dType;

class Stack {
  public:
    this()
    {
      top = -1;
    }
    ~this(){}
    int getTop()
    {
      return thisStack[top];
    }
    void pop()
    {
      top--;
    }
    void push(dType newData)
    {
      thisStack[++top]= newData;
    }
  private:
    int top;
    dType[30] thisStack;
}

int main()
{
  Stack myStack = new Stack;

  for( int i = "A"; i <= "z"; ++i )
  {
    myStack.push(i);
  }

  for( int i = myStack.top ; i > -1 ; --i)
  {
    printf("%d\t%c\n", myStack.top, myStack.getTop());
    myStack.pop();
  }
  return 0;
}

In C++ I would do the following:

template <class Stack>
cass Stack{
    ...
}

I would use it in the following way:

Stack<double> dStack;

does D only support function templates or is there a way to do this with classes?

Thanks,
Andrew

"Andrew Edwards" <edwardsac@spamfreeusa.com> wrote in news:bd29ja$2bqc$1@digitaldaemon.com:

> What follows is a simple use of the stack ADT. I have two questions: 1) How do I make the Stack class a template? 2) Why is it possible to access the variable "top" from within main?

1)
Thanks to your alias "dType", it was a piece of cake to make a template
from your code :)

template NeverKnowHowToNameThis(dType)
{
   class Stack {
    ...  // no changes here
   }
}


int main()
{
   // use explicit type naming for template class
   alias instance NeverKnowHowToNameThis(int).Stack Stack_int;
   Stack_int myStack = new Stack_int;

   // another way - no type naming this time
   instance NeverKnowHowToNameThis(int).Stack anotherStack
      = new instance NeverKnowHowToNameThis(int).Stack;

   for( int i = "A"; i <= "z"; ++i )
   {
      myStack.push(i);
   }

   for( int i = myStack.top ; i > -1 ; --i)
   {
      printf("%d\t%c\n", myStack.top, myStack.getTop());
      myStack.pop();
   }
   return 0;
}



2) Everything within the same module has access to private & protected (class) members.

After changing the Stack class to a template, the private members can no longer be accessed in main(). I think, that's just a bug in DMD 0.66(Win) and not by intention.



Farmer.



> 
> Thanks,
> Andrew
> 
> //import stream;
> alias int dType;
> 
> class Stack {
>   public:
>     this()
>     {
>       top = -1;
>     }
>     ~this(){}
>     int getTop()
>     {
>       return thisStack[top];
>     }
>     void pop()
>     {
>       top--;
>     }
>     void push(dType newData)
>     {
>       thisStack[++top]= newData;
>     }
>   private:
>     int top;
>     dType[30] thisStack;
> }
> 
> int main()
> {
>   Stack myStack = new Stack;
> 
>   for( int i = "A"; i <= "z"; ++i )
>   {
>     myStack.push(i);
>   }
> 
>   for( int i = myStack.top ; i > -1 ; --i)
>   {
>     printf("%d\t%c\n", myStack.top, myStack.getTop());
>     myStack.pop();
>   }
>   return 0;
> }
> 
> 

That works! Thanks alot.

Andrew

The below is a modified version of the previous program,
in an attempt to evaluate infix-expressions.
While testing the program I encountered two errors:
With the following expressions:

    (3*4)*(5/2 ) I get: "ValidError: ArrayBoundsError stack.d(13)"
and
    (3*4)*(5/2) I get: "Error: ArrayBoundsError stack.d(13)"

All other combinations of the expression produce the correct output. I'm having a little problem understanding why! Any assistance would be greatly appreciated.

Additionally is there anyway to truncate a D string one character at a time other than through slicing? I think this would be helpful. Then again I'm just a beginner, so I may not be seeing the big picture. My thought is this: if I can truncate a string, then I can use array.length to identify the top of a stack, when I pop off an item, the the last item in the array gets truncated. Thus, the only variable I'd need to access the top of the stack is stack.length.

I don't know if this makes sense to anyone else but me. Please advise. Andrew

----------------
file: stack.d
----------------
module stack;

template _Stack(dType){
  class Stack {
    public:
      this()
      {
        top = -1;
      }
      ~this(){}
      dType getTop()
      {
        return thisStack[top];
      }
      void pop()
      {
        top--;
        thisStack = thisStack[0..(thisStack.length - 1)];
      }
      void push(dType newData)
      {
        top++;
        thisStack ~= newData;
      }
      bit isEmpty()
      {
        return (thisStack.length == 0);
      }
      int size()
      {
        return top;
      }
    private:
      int top;
      dType[] thisStack;
  }
}

----------------
file: testStack.d
----------------
import stream;
import stack;

int main()
{
  alias instance _Stack(char).Stack dStack;
  dStack myStack = new dStack;
  char[] ch;

  printf("Enter an expression to be analized:"\n);
  stdin.scanf("%.*s", &ch);

  for( int i = ch.length - 1; i > -1; --i )
  {
    switch(ch[i])
    {
      case "[":
      case "{":
      case "(":
        myStack.push( ch[i] );
      case "]":
      case "}":
      case ")":
      {
        if(myStack.getTop() == "[" ||
           myStack.getTop() == "{" ||
           myStack.getTop() == "(" )
        {
          myStack.pop();
          printf("Valid");
        }
        else
        {
          myStack.pop();
          printf("Invalid");
        }
      }
      default:{}
    }
  }

  for( int i = myStack.size(); i > -1; --i)
  {
    printf("%d\t%c\n", i, myStack.getTop());
    myStack.pop();
    if(myStack.isEmpty())
      printf("The stack is now empty!\n");
  }
  return 0;
}

Note: the above code may contain errors.

Hello Andrew,

are you sure you posted the correct code?
What expressions produce the correct output?

If you enter (3*4)*(5/2) then your code finds ')' at the end of ch[] and
tries to pop sth. from an *empty* stack. Ouch.
Your switch statement has no breaks. Is this by intention? If so, then better
write a comment saying "nobreak". Makes it life easier for maintainers.

> if I can truncate a string, then I can use array.length to identify the top of a stack, when I pop off an item, the the last item in the array gets truncated. Thus, the only variable I'd need to access the top of the stack is stack.length.
You do not need the top of stack variable as you can change the array length
by slicing it.
<quote from your code>
    thisStack = thisStack[0..(thisStack.length - 1)];
<quote from your code/>

That works perfecty.


Farmer.

"Andrew Edwards" <edwardsac@spamfreeusa.com> wrote in news:bd601l$2t7o$1@digitaldaemon.com:

> The below is a modified version of the previous program,
> in an attempt to evaluate infix-expressions.
> While testing the program I encountered two errors:
> With the following expressions:
> 
>     (3*4)*(5/2 ) I get: "ValidError: ArrayBoundsError stack.d(13)"
> and
>     (3*4)*(5/2) I get: "Error: ArrayBoundsError stack.d(13)"
> 
> All other combinations of the expression produce the correct output. I'm having a little problem understanding why! Any assistance would be greatly appreciated.
> 
> Additionally is there anyway to truncate a D string one character at a time other than through slicing? I think this would be helpful. Then again I'm just a beginner, so I may not be seeing the big picture. My thought is
this:
> if I can truncate a string, then I can use array.length to identify the top of a stack, when I pop off an item, the the last item in the array gets truncated. Thus, the only variable I'd need to access the top of the stack is stack.length.
> 
> I don't know if this makes sense to anyone else but me. Please advise. Andrew
> 
> ----------------
> file: stack.d
> ----------------
> module stack;
> 
> template _Stack(dType){
>   class Stack {
>     public:
>       this()
>       {
>         top = -1;
>       }
>       ~this(){}
>       dType getTop()
>       {
>         return thisStack[top];
>       }
>       void pop()
>       {
>         top--;
>         thisStack = thisStack[0..(thisStack.length - 1)];
>       }
>       void push(dType newData)
>       {
>         top++;
>         thisStack ~= newData;
>       }
>       bit isEmpty()
>       {
>         return (thisStack.length == 0);
>       }
>       int size()
>       {
>         return top;
>       }
>     private:
>       int top;
>       dType[] thisStack;
>   }
> }
> 
> ----------------
> file: testStack.d
> ----------------
> import stream;
> import stack;
> 
> int main()
> {
>   alias instance _Stack(char).Stack dStack;
>   dStack myStack = new dStack;
>   char[] ch;
> 
>   printf("Enter an expression to be analized:"\n);
>   stdin.scanf("%.*s", &ch);
> 
>   for( int i = ch.length - 1; i > -1; --i )
>   {
>     switch(ch[i])
>     {
>       case "[":
>       case "{":
>       case "(":
>         myStack.push( ch[i] );
>       case "]":
>       case "}":
>       case ")":
>       {
>         if(myStack.getTop() == "[" ||
>            myStack.getTop() == "{" ||
>            myStack.getTop() == "(" )
>         {
>           myStack.pop();
>           printf("Valid");
>         }
>         else
>         {
>           myStack.pop();
>           printf("Invalid");
>         }
>       }
>       default:{}
>     }
>   }
> 
>   for( int i = myStack.size(); i > -1; --i)
>   {
>     printf("%d\t%c\n", i, myStack.getTop());
>     myStack.pop();
>     if(myStack.isEmpty())
>       printf("The stack is now empty!\n");
>   }
>   return 0;
> }
> 
> Note: the above code may contain errors.
> 
>