Using a stack to compare a string

This is a discussion on Using a stack to compare a string within the C++ Programming forums, part of the General Programming Boards category; Hey there....Homework time again... As always I dont expect you to do my homework I just need a kick in ...

  1. #1
    Registered User
    Join Date
    Sep 2006
    Location
    Martin, Tn
    Posts
    12

    Using a stack to compare a string

    Hey there....Homework time again... As always I dont expect you to do my homework I just need a kick in the right direction... The instructions from my teacher are as follows

    Code:
    Program 4
    Fall 2006
    In Stack.h and Stack.o you have a header file for a Stack class. Note that this is slightly different from the text in that all operations such
    as Push, Pop etc. begin with an upper case letter. Be sure to note this if you elect to use this header file. There are also some meber
    functions not implemented in the text or slightly different, such as Print and Full.
    Using this header file and Stack.o (precompiled version of the Stack class), or implementing the stack class on your onw, write a program
    to test to see if strings of parentheses, square brackets and curly braces are balanced. When you find a string is unbalanced at some stage,
    you should print the contents of the stack at the time the error occured and print the original string.
    For example
    (() is not balanced
    []{}([]) is balanced
    {{([])[]}} is balanced
    etc.
    The srings to be tested are in balanced.txt. You may alter this file by adding a $-sign to the end of each string if you would like.
    I have the code working except one small prob and I cant find it, I have stared at it for a LONG time and cant figure it out. Here is my code and the output I get from it.

    Code:
    Line #   Statement
    ------   ---------
     0001    /*
     0002        Program: Stack Balance
     0003     Programmer:
     0004           Date: Nov 7, 2006
     0005    Description: Reads information from a file , then checks to see if the
     0006                 info is balanced and prints accordingly.
     0007    */
     0008    
     0009    #include <iostream>
     0010    #include "stackt.h"
     0011    #include <fstream>
     0012    using namespace std;
     0013    
     0014    const int MAX = 81;
     0015    typedef char String[MAX];
     0016    
     0017    void getline(ifstream &ifs, String &x, int &length);
     0018    void checkLine(String x, int length);
     0019    
     0020    // ========================================================
     0021    int main(void)
     0022    {
     0023           ifstream fin;
     0024        fin.open("balanced.txt");
     0025           int a = 5;
     0026           while(a >=0)
     0027           { 
     0028         String x;
     0029         int length = 0;
     0030    
     0031      
     0032         getline(fin,x,length);
     0033         checkLine(x, length);
     0034         a--;
     0035        }
     0036    cout << endl;
     0037    system ("pause");
     0038      return 0;
     0039    }
     0040    
     0041    
     0042    // ========================================================
     0043    void getline(ifstream &ifs, String &x, int &length)
     0044    {
     0045           int i = 0;
     0046           char ch;
     0047    
     0048     ifs.get(ch);
     0049     while (i < MAX && (ch != '$'))
     0050     {
     0051            cout << ch;
     0052            x[i] = ch;
     0053            i++;
     0054            length++;
     0055            ifs.get(ch);
     0056     }
     0057     cout << ch << endl; 
     0058     return;
     0059    }
     0060    
     0061    
     0062    // ========================================================
     0063    void checkLine(String x, int length)
     0064    {
     0065        Stack <char> s;
     0066    
     0067     char ch;
     0068     char temp;
     0069     bool balanced = true;
     0070     int i = 0;
     0071    
     0072     ch  = x[i];
     0073     while( i < length)
     0074     {
     0075       if(ch == '(' || ch == '{' || ch == '[')
     0076            {
     0077              s.push(ch);
     0078            }
     0079    
     0080       if(ch == ')' || ch == '}' || ch == ']')
     0081            {
     0082           if(s.empty())
     0083               {
     0084                      cout << "Unmatched closing bracket: " << ch << endl;
     0085               }
     0086    
     0087              else
     0088              {
     0089                    temp =  s.top( );
     0090                      s.pop();
     0091    
     0092               balanced = (ch == ')' &&  temp == '(') || (ch == '}' && temp == '{') || (ch == ']' && temp == '[');
     0093    
     0094                if(!balanced)
     0095                    {
     0096                     cout << "Bad match between: " << temp << " and " << ch <<endl;
     0097                    }
     0098             }
     0099       }
     0100    
     0101            i++;
     0102            ch = x[i];
     0103           
     0104           if ((balanced) && (ch == '#') && (!s.empty()))
     0105              cout << "Unmatched bracket...String Not balanced" << endl;
     0106     }
     0107     return;
     0108    }
    
    --- Compiling balanced.cpp...
    
    --- Compilation successful...
    
    --- Execution begins...output is program's...
    
    ((())){()}[]$
    
    (({})())[]$
    
    {{()}]$
    Bad match between: { and ]
    
    (()))$
    Unmatched closing bracket: )
    
    []{}()({[]()})$
    
    ((())$
    
    sh: pause: command not found
    
    --- Execution terminated.
    My problem is that it works until the last string of Braces Brackets and parenthesis, The last one isnt balanced but yet it shows as being balanced. I have looked for this prob for more than 8 Hrs just on this one problem...I was thinking that maybe a fresh pair of eyes will help me see where I messed up.

    Also I wrote my own Stack header file instead of using the one that the teacher provided cuz his was all kinda screwy...Here is my Stack Header file

    Code:
    #include <iostream>
    #ifndef STACKT
    #define STACKT
    using namespace std;
    
    const int STACK_CAPACITY = 128;
    template <class StackElement>
    
    class Stack
    {
     //****** Function Members ******
      public:
             Stack();
    
    //****** Stack Empty ******
    bool empty() const;
    
    //****** Add a value to the stack ******
    void push(const StackElement& value);
    
    
    //****** Display values stored in the stack ******
    void display (ostream& out) const;
    
    
    //****** Return value at top of the stack ******
    StackElement top() const;
    
    
    //****** Remove value at top of the stack ******
    void pop();
    
    
    //****** Data Members ******
       private:
               StackElement myArray[STACK_CAPACITY];
               int myTop;
    }; // end of class declaration
    
    
    // ---definition of Constructor ******
    template <class StackElement>
    inline Stack<StackElement>::Stack()
    {myTop = -1;}
       
    
    //****** definition of empty( ) ******
    template <class StackElement>
    bool Stack<StackElement>::empty() const
    {
      return (myTop == -1);
    }
    
    
    //****** definition of push( ) ******
    template <class StackElement>
    void Stack<StackElement>::push(const StackElement& value)
    {
     if (myTop < (STACK_CAPACITY - 1))
      {
       ++myTop;
       myArray[myTop] = value;
      }
     else
     {
      cerr << "***Stack is full -- can not add new value ***\n";                  
        cerr << "Must increase value of STACK_CAPACITY in stackT.h\n";
     }
    } // push
    
    
    //****** definition of display( ) ******
    template <class StackElement>
    void Stack<StackElement>::display(ostream& out) const
     {
      for (int i = myTop; i >= 0; i--)
        out << myArray[i] << endl;
     }
    
    
    //****** definition of top( ) ******
    template <class StackElement>
    StackElement Stack<StackElement>::top() const
     {
      if (myTop >= 0)
        return myArray[myTop];
      cerr << "*** Stack is empty ***\n";
      }
    
    
    //****** definition of pop( ) ******
    template <class StackElement>
    void Stack<StackElement>::pop()
     {
      if (myTop >= 0)
         myTop--;
      else
          cerr << "*** Stack is empty -- can not remove a value ***\n";
     }
    #endif
    Thanks in advance for the help... I hope someone can find it for me.

  2. #2
    Registered User
    Join Date
    Oct 2001
    Posts
    2,934
    >0104 if ((balanced) && (ch == '#') && (!s.empty()))
    Shouldn't this instead be:
    Code:
    if ((balanced) && (ch == '$') && (!s.empty()))

  3. #3
    Registered User
    Join Date
    Sep 2006
    Location
    Martin, Tn
    Posts
    12
    Oops...I had corected that since I posted the code... It still didnt correct my problem. The prog still does not show the last string of characters as unbalanced...

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. String Class
    By BKurosawa in forum C++ Programming
    Replies: 117
    Last Post: 08-09-2007, 01:02 AM
  2. Program using classes - keeps crashing
    By webren in forum C++ Programming
    Replies: 4
    Last Post: 09-16-2005, 03:58 PM
  3. Something is wrong with this menu...
    By DarkViper in forum Windows Programming
    Replies: 2
    Last Post: 12-14-2002, 10:06 PM
  4. ........ed off at functions
    By Klinerr1 in forum C++ Programming
    Replies: 8
    Last Post: 07-29-2002, 09:37 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21