Matching Brackets


This is a companion discussion topic for the original entry at https://toph.co/p/matching-brackets

why RTE?can’t understand:(

#include<bits/stdc++.h>
using namespace std;
int main(void){
    string s;
    getline(cin, s);
    stack<char>a;
    if(s.length()==0){
        printf("No\n");
        return 0;
    }
    for(int i=0;i<s.length(); i++){
        if(s[i]=='('||s[i]=='{'||s[i]=='['){
            a.push(s[i]);
        }else{
            if(a.empty()){
                printf("No\n");
            }
            if(s[i]==')'){
                if(a.top()=='(')
                    a.pop();
            }
            if(s[i]=='}'){
                if(a.top()=='{')
                    a.pop();
            }
            if(s[i]==']'){
                if(a.top()=='[')
                    a.pop();
            }
        }
    }
    if(a.empty())printf("Yes\n");
    else printf("No\n");
}

In line 15 to 17.

if(a.empty()){
    printf("No\n");
}

Even if a is empty, the code does not exits, resulting in the code attempting to access the top of an empty stack and producing Runtime Error.
You can avoid it by adding

return 0;

inside the if statement.

tnx… that worked…^.^

#include<bits/stdc++.h>
using namespace std;

int main()
{
    char ara[100], str[100];
    int a=0, b=0, c=0, len, top=0;
    scanf("%[^\n]", ara);
    len = strlen(ara);
    for(int i=0; i<len; i++) {
        if(ara[i] == '(' || ara[i] == '{' || ara[i] == '[') {
            str[top++] = ara[i];
           }
        else {
            if(top == 0) {
                cout<<"No\n";
                return 0;
            }
            top--;
            if(ara[i] == ')') {
                if(str[top] != '(') {
                cout<<"No\n";
                return 0;
                }
            }
            else if(ara[i] == '}') {
                if(str[top] != '{') {
                cout<<"No\n";
                return 0;
                }
            }
            else if(ara[i] == ']') {
                if(str[top] != '[') {
                cout<<"No\n";
                return 0;
                }
            }
        }
    }

    cout<<"Yes\n";

    return 0;
}

Getting WA for the last test case :sweat_smile:

Of course, you will, you did not check the top after the loop exits.

Test your code for this kind of input.

[{()}]{

thanks…that worked :heart_eyes:

1 Like

#include<bits/stdc++.h>
using namespace std;
#define size 1000
int i,j,l;
char s[1000];

struct stack
{
char stk[size];
int top;
}str;

void push(char value)
{
str.top++;
str.stk[str.top]=value;
}

void pop()
{
str.top–;
}

int main()
{
str.top=0;
scanf("%s", s);
i=0;

if(strlen(s)==0){
    printf("No\n");
    return 0;
}
while(s[i]!='\0')
{
    if(s[i]=='(' || s[i]=='{' || s[i]=='[')
        push(s[i]);
    else if(s[i]==')' || s[i]=='}' || s[i]==']')
    {
        if(s[i]==')')
            if(str.stk[str.top]=='(')
               pop();

        if(s[i]=='}')
            if(str.stk[str.top]=='{')
               pop();

        if(s[i]==']')
            if(str.stk[str.top]=='[')
               pop();
    }
    i++;


}
    if(str.top == 0)
        printf("Yes");
    else
        printf("No");

return 0;

}

getting WA on 7th Test case

    Scanner in=new Scanner(System.in);
    String n=in.nextLine();
    char a[]=n.toCharArray();
    int top=0;
    int size =a.length;
    char stack[]=new char[size];
    if(size==0){
        System.out.println("No");
        System.exit(0);
    }
    for (int i = 0; i <size; i++) {
        if((a[i]=='(')||(a[i]=='{')||(a[i]=='[')){
            top++;
            stack[top]=a[i];
        }else{
            if(top==0){
                System.out.print("No");
                System.exit(0);
            }else if(a[i]==')'){
                  if(stack[top]=='('){
                        top--;
                    }
            }else if(a[i]=='}'){
                  if(stack[top]=='{'){
                        top--;
                    }
            }else if(a[i]==']'){
                    if(stack[top]=='['){
                        top--;
                    }
                }
        }
    }
    if(top==0){
        System.out.println("Yes");
    }else{
        System.out.println("No");
    }

RTE 8th case why

@hjr265
This problem has poor data sheet.
For “())“0r”()))” ,answer is “No”.BUT,my program print “Yes” for this kind of cases(with extra closing brackets in the end) and I got “Accepted”. :slightly_smiling_face: .
But i should have got WA.

2 Likes

Thank you for reporting this, @sorcerer. Test cases of this problem have been updated.

What’s wrong in my COde

using System;
using System.Collections;
namespace ConsoleApplication3
{
	public class MatchBracket
    {
		public Boolean matched(char chr1, char chr2)
        {
			if (chr1 == '(' && chr2 == ')') return true;
			else if (chr1 == '{' && chr2 == '}') return true;
			else if (chr1 == '[' && chr2 == ']') return true;
			else
			return false;
        }
		public string isblanced(string str)
        {
			Stack<char> stack = new Stack<char>();
			for(int i = 0; i < str.Length; i++)
            {
				if(str[i] == '(' || str[i] == '{' || str[i] == '[')
                {
					stack.Push(str[i]);
                }	
				else if(str[i] == ')' || str[i] == '}' || str[i] == ']')
                {
					if (stack.Count == 0) return "NO";
					else if (!matched(stack.Pop(), str[i])) return "NO";    
                }
            }
			if (stack.Count == 0) return "YES";
			else return "NO";
		}
    }

	class Program
	{
		static void Main(string[] args)
		{
			string str1 = Console.ReadLine();
			MatchBracket obj = new MatchBracket();
			Console.WriteLine(obj.isblanced(str1));
		}
	}
}

Your code seems logically correct.

The only issue I see is that you are using a generic stack, but you are not using System.Collections.Generic.

Add a .Generic to your second import. Like so:

using System.Collections.Generic;