Asking about the parenthesis matching in c++

Question

I'm currently working on my first datastructure homework

The topic is "parenthesis matching"

The answer in my mind is simple,

just push the opening parenthesis to the stack , and when you meet the closing parenthesis pop it out.

After finishing my code , I submit it to our school's online judgement system

Only get 9 corrects out of 10 questions.

Here's my c++ code

Is there any situation that I missed in this code?? Thank you all!

/Question's here/ The question is that input a integer N < 1000 which means the testcases

and following N strings length < 1000 should be tested if it's a valid string

If yes , output Case N(from 1~N):Yes

No , output Case N(from 1~N):No

string may contain newline character

#Test cases

Input

2

[][]<>()[{}]

<{>}

Output

Case 1: Yes

Case 2: No

#include <iostream>
#include <string>
using namespace std;

class PARENTHE
{
public:

 PARENTHE(int slength);
 ~PARENTHE();

 int StackSize() const;

 bool StackEmpty() const;

 char top() const;

 void Push(const char);
 void Pop();

private:
 char *str;
 int slength;
 int stop;

};

PARENTHE::PARENTHE(int slength)
{

    str = new char [slength];
    stop = -1;
}

PARENTHE::~PARENTHE()
{ delete [] str; }

inline int PARENTHE::StackSize() const
{ return stop+1; }

inline bool PARENTHE::StackEmpty() const
{
    return (stop == -1);
}

inline char PARENTHE::top() const
{ return str[stop]; }

void PARENTHE::Push(const char c)
{
     str[++stop] = c;
}

void PARENTHE::Pop()
{
     stop--;
}



int main()
{
    int t;

    while( cin>>t )
    {

       int i = 0;

       while( i < t )
         {

            string temp;
            cin>>temp;

            if(temp == "\n")
            {
                cout<<"Case "<<++i<<": "<<"Yes"<<endl;
                break;
            }

            PARENTHE S( 1001 );

            bool check = false;

            for( int it = 0; it < temp.size() ; ++it )
            {

                if( temp[it] == '{' || temp[it] == '[' || temp[it] == '(' || temp[it] == '<' )
                    S.Push(temp[it]);

                else if ( temp[it] == '}' || temp[it] == ']' || temp[it] == '>' || temp[it] == ')' )
                {
                    if(!S.StackEmpty())
                    {
                    if(( S.top() == '{' && temp[it] == '}' ) || ( S.top() == '(' && temp[it] == ')' ) || ( S.top() == '[' && temp[it] == ']' ) || ( S.top() == '<' && temp[it] == '>' ) )
                            {
                                S.Pop();
                            }

                    else { break; }

                    }

                    else { break; }


                }

                if ( it == (temp.size()-1) && (!S.StackSize()))
                {
                   check = true;
                }

            }
            if(check)
                cout<<"Case "<<++i<<": "<<"Yes"<<endl;

            else
                cout<<"Case "<<++i<<": "<<"No"<<endl;

       }
     }

    return 0;
}

Does your testing string contain spaces? http://stackoverflow.com/questions/5838711/c-cin-input-with-spaces — CiaPan, Mar 21 '14 at 07:06
I don't get a proper o/p for your program. Can you edit your question to include a sample testcase — Vishal R, Mar 21 '14 at 07:18
may be following coding style is also tested? UPPER_CASE identifieers normally are reserved for macros and defines. Classes normally use UpperCamelCase and instances lowerCamelCase — vlad_tepesch, Mar 21 '14 at 07:19
I would subtract points for rolling your own stack instead of using std::stack :) — heinrichj, Mar 21 '14 at 07:34
@heinrichj I'm just practicing the method of class in c++ , cause I learned C before :) — F.LCY, Mar 21 '14 at 09:08
@CiaPan thanks for noticing , but if I use getline , my while loop would screw up — F.LCY, Mar 21 '14 at 10:00
Onse you have read `t` you know that there is exactly `t` lines to read, so just do `for( int i = 0; i < t; i++) { getline...; proces a line }` — CiaPan, Mar 21 '14 at 10:44
After I use getline to receive my data , the answer still comes out 9 correct out of 10 ...! But still really appreciated!!! Big thanks! @CiaPan — F.LCY, Mar 21 '14 at 11:15
@vlad_tepesch I've corrected my coding style , thanks for noticing :) but still 9/10... — F.LCY, Mar 21 '14 at 11:17
Read carefully the second `if`, which tests for closing parentheses and the instructions below it. What happens if the input string is a single closing paren, say ")"? — CiaPan, Mar 21 '14 at 11:25
I think single closing paren would go into else (which StackEmpty()= true) the whole loop will break; And check remains false. :) — F.LCY, Mar 21 '14 at 11:29
Yes, you're right, my fault. I'm sorry, I got lost in mismatching indentation and missed one of `else-break` branches. So the code to check parens looks correct for me. It definitely should give a correct answer on the processed string. If it doesn't, possibly it does not process some string? A decision is made on the last character of a string, so the question is: what happens if the string doesn't have the last character? Empty string is correct, but may be your program inorrectly handles it? Try changing the first `if` in `main` to `if(temp == "\n" || temp == "")` or something equivalent. — CiaPan, Mar 22 '14 at 13:36
I think I know where the question is. I've done 10 correct since I change the for loop to ( i = 0 ; i <= temp.size() ; i++) — F.LCY, Mar 23 '14 at 11:21

score 0 · Answer 1 · answered Mar 21 '14 at 07:26

0

I would advice You to check the reverse polish notation, it'll handle all Your problems.

answered Mar 21 '14 at 07:26

Maciej Lichoń

157
5

Asking about the parenthesis matching in c++

1 Answers1