www.digitalmars.com         C & C++   DMDScript  

D - template(T) pushdownStack && postfix/infix-expressions

reply "Andrew Edwards" <edwardsac spamfreeusa.com> writes:
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
Jun 18 2003
next sibling parent reply "Carlos Santander B." <carlos8294 msn.com> writes:
"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
Jun 18 2003
parent reply "Andrew Edwards" <edwardsac spamfreeusa.com> writes:
"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)
Jun 19 2003
parent "Carlos Santander B." <carlos8294 msn.com> writes:
"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
Jun 19 2003
prev sibling next sibling parent reply "Andrew Edwards" <edwardsac spamfreeusa.com> writes:
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;
}
Jun 21 2003
next sibling parent "Andrew Edwards" <edwardsac spamfreeusa.com> writes:
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
Jun 21 2003
prev sibling parent reply Farmer <itsFarmer. freenet.de> writes:
"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;
 }
 
 

Jun 21 2003
parent "Andrew Edwards" <edwardsac spamfreeusa.com> writes:
That works! Thanks alot.

Andrew
Jun 21 2003
prev sibling parent reply "Andrew Edwards" <edwardsac spamfreeusa.com> writes:
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.
Jun 22 2003
next sibling parent Farmer <itsFarmer. freenet.de> writes:
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.

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 

 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.
 
 

Jun 24 2003
prev sibling parent reply Farmer <itsFarmer. freenet.de> writes:
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.

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 

 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.
 
 

Jun 24 2003
parent reply "Andrew Edwards" <edwardsac spamfreeusa.com> writes:
"Farmer" wrote ...
 Hello Andrew,

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

Hello, Thanks for your help thus far. Please bear with me as I try to understand how this is all supposed to work. Your comments have forced me to conduct an extensive reevaluation of exactly what I was doing in the code presented earlier. I discovered that my thoughts on how scanf() worked was flawed. There was no way to evaluate any expression provided unless it was void of spaces because scanf() returns when it encounters a whitespace. Further review of stream.d uncovered the readLine() function which prompted a complete rewrite of testStack.d. I have attached the resulting files. There are a number of errors in testStack.d that I do not understand how to fix. Please advise. On the subject of break, would it not be better to require a break statement? Then, if the programmer desires not to use break, he/she can specify nobreak or fallthrough. I must admit, I did not realize that I had not provided break statements. Andrew
Jun 25 2003
next sibling parent "Andrew Edwards" <edwardsac spamfreeusa.com> writes:
sorry!! code attached!
Jun 25 2003
prev sibling next sibling parent reply Farmer <itsFarmer. freenet.de> writes:
 On the subject of break, would it not be better to require a break
 statement? Then, if the programmer desires not to use break, he/she can
 specify nobreak or fallthrough. I must admit, I did not realize that I had
 not provided break statements.

This topic has been discussed serveral times. Certainly, forcing use of nobreak or fallthrough would clutter code somewhat: case '[': nobreak; case '{': nobreak; case '(': myStack.push(expression[i]); break; case ']': Personally, I find the way C# solves this issue most compelling. In C# the "nobreak" statement (actually it is a goto statement in C#) is only needed in those cases that look like bugs. E.g. When writing case '[': case '{': case '(': myStack.push(expression[i]); case ']': the C# compiler issues an error for the line containing "myStack.push(expression[i]);".
 what I was doing in the code presented earlier. I discovered that my
 thoughts on how scanf() worked was flawed. There was no way to evaluate any
 expression provided unless it was void of spaces because scanf() returns
 when it encounters a whitespace.

I admit that when I saw scanf() I felt uncomfortable, so I immediately replaced it by readLine(), before testing your code.
 There are a number of errors in testStack.d that I do not understand how to
 fix. Please advise.

The order of statements in the code is often confusing. The execution order of statements is very important both for correctness and ease of understanding, lazyness isn't any good here. void pop() { thisStack = thisStack[0..(thisStack.length - 1)]; if (isEmpty()) thisStack = ""; } 1) That certainly doesn't work. (wrong execution order) 2) When the stack is empty, throwing an exception could be a good idea. Ignoring errors makes debugging painful and your code less robust. Trying to return some special value for errors usually has similar consequences. 3) Stack isn't reusable, since you use strings to set the stack to an empty array. If you need an empty array, you can use new dType[0]. Why does the main code not work? Use of variable balance is wrong. If you use goto unbalanced instead of continue then it could work, as balance is superflous then, anyway. The line that contains the real bug is this one: if(myStack.isEmpty() || myStack.size() == 1) Error checking is still incomplete. Best is to check for all possible (expected) errors in your main code and to additionally throw exceptions in your Stack class for any error condition. Since the Stack class is mapped to a (bound-checked) D-array, you could omit explicit checks in the Stack class, for most methods. Farmer.
Jun 26 2003
parent reply Bill Cox <bill viasic.com> writes:
Farmer wrote:
On the subject of break, would it not be better to require a break
statement? Then, if the programmer desires not to use break, he/she can
specify nobreak or fallthrough. I must admit, I did not realize that I had
not provided break statements.

This topic has been discussed serveral times. Certainly, forcing use of nobreak or fallthrough would clutter code somewhat: case '[': nobreak; case '{': nobreak; case '(': myStack.push(expression[i]); break; case ']': Personally, I find the way C# solves this issue most compelling. In C# the "nobreak" statement (actually it is a goto statement in C#) is only needed in those cases that look like bugs. E.g. When writing case '[': case '{': case '(': myStack.push(expression[i]); case ']': the C# compiler issues an error for the line containing "myStack.push(expression[i]);".

I'm guessing I'm in the main-stream of opinion on this group by calling for such an extension. I hate those bugs caused by leaving out the break statement. Bill
Jun 27 2003
parent "Sean L. Palmer" <palmer.sean verizon.net> writes:
Yes, very much so.  We just need someone to build an airtight case, or
someone to threaten Walter's kneecaps.  ;)

He really doesn't want to go against established C doctrine, but I can't for
the life of me figure out why he diverges from C in, say, type specifier
syntax, and then refuses a badly needed, universally wanted change on the
grounds of C syntax incompatibility.  Or maybe because it adds a new
keyword.

C# proves it can be fixed with minimal headaches.  Old code still compiles,
except for the rare Duff device which needs to have explicit fallthru's
added to shut the compiler up.  I don't see what the problem is.

Sean

"Bill Cox" <bill viasic.com> wrote in message
news:3EFCA034.6030401 viasic.com...
 Farmer wrote:
On the subject of break, would it not be better to require a break
statement? Then, if the programmer desires not to use break, he/she can
specify nobreak or fallthrough. I must admit, I did not realize that I



not provided break statements.

This topic has been discussed serveral times. Certainly, forcing use of nobreak or fallthrough would clutter code somewhat:


 I'm guessing I'm in the main-stream of opinion on this group by calling
 for such an extension.  I hate those bugs caused by leaving out the
 break statement.

 Bill

Jun 29 2003
prev sibling parent "Sean L. Palmer" <palmer.sean verizon.net> writes:
We've argued this til we're blue in the face.  Walter won't budge.

Sean

"Andrew Edwards" <edwardsac spamfreeusa.com> wrote in message
news:bddcib$6qi$1 digitaldaemon.com...
 On the subject of break, would it not be better to require a break
 statement? Then, if the programmer desires not to use break, he/she can
 specify nobreak or fallthrough. I must admit, I did not realize that I had
 not provided break statements.

 Andrew

Jun 29 2003