Kiểm tra dãy n các dấu ngoặc là đúng hay sai?

[thucuc1710]

Em có bài này mà không biết làm như thế nào, mọi người giúp em với nhé!
Đề bài: Nhập vào số nguyên n, sau đó nhập n dấu ngoặc với 1<n<=20
Yêu cầu là kiểm tra dãy dấu ngoặc đó là đúng hay sai!
Em chỉ có thể làm được kiểm tra dãy dấu ngoặc bất kì thôi, còn số nguyên n thì em chịu chết!
thanks trc nhé

[vuthanhtrung90]

Mình chưa hiểu đề lắm. Bạn có thể cho ví dụ được không?

[thucuc1710]

Vd: N=4 (()): đúng
n=6 ()())): Sai

[lttq]

giống bài tập automat hồi năm 2 làm.Dùng cây cú pháp để xử lý dấu ngoặc.

[tiendaotd]

bạn tìm dấu ngoặc đúng đầu tiên ( cặp đơn vị ). Xóa cặp đơn vị này. Lặp lại quá trình tới khi không thể xóa được nữa. Lúc này nếu số dấu ngoặc = 0 thì đúng, ngược lại là sai.

[nmt1402]

Năm 2 làm còn cái code này, tham khảo nhé, chạy trên linux

/*Algorithm: 1:make an empty stack2: while (end of input is not reach){  - if symbol read not a symbol to be balanced, ignore if  - If the character is an opening symbol , push it onto the stack  - If it is a clodeing symbol, the nif the stack is empty return 0, otherwise pop th srack  - if the symbol poped is not the corresponding opeing symbol, report an errorIn the end of output, return 1 if a->top = 0 else return 1 */#include <stdio.h>#include <string.h>#include <stdlib.h>#define MAX 20 struct stack{  char character[MAX];  int top;}; typedef struct stack stack; void Init(stack *a){  a->top=0;} void Push(stack *a,int value){  if(a->top>=MAX){    printf("canot push more element to stack.\n");    exit(1);  }  else{    a->top++;    a->character[a->top]=value;  }} int Pop(stack *a){  if(a->top<=0){    printf("cannot pop more ..\n");    exit(1);  }  else{    int temp=a->character[a->top];    a->top--;    return temp;  }} int check(stack *a,char *str){  int i;  int count=0;  for(i=0;i<strlen(str);i++){  //liner    if((str[i]=='(')||(str[i]=='{')||(str[i]=='['))      Push(a,str[i]);    else if(str[i]==')'){      if(a->top!=0){            if(Pop(a)!='(')  //      return 0;      }      else    Push(a,str[i]);     }    else if(str[i]=='}'){      if(a->top!=0){    if(Pop(a)!='{')      return 0;      }      else    Push(a,str[i]);     }  else if(str[i]==']'){    if(a->top!=0){      if(Pop(a)!='[')    return 0;    }    else      Push(a,str[i]);   }  else if(str[i]=='"'){    count++;   //count the number of " character    if(count%2!=0){    //check odd or even      Push(a,str[i]);  // if odd    }    else{      if(Pop(a)!='"')    return 0;    }  }  }  if(a->top==0)    return 1;  else    return 0;}    int main(){  stack a;  Init(&a);  char str1[20];  printf("input the expression operator:");  fgets(str1,20,stdin);  if(check(&a,str1))    printf("Well done.Correct parentness!\n");  else    printf("wrong, parentness!\n");}

[tiendaotd]

#include<cstdio>#include<iostream>#include<sstream>#include<algorithm>#include<cstring>#include<string>#include<cstdlib>#include<vector>#include<bitset>#include<stack>#include<queue>#include<deque>#include<cmath>#include<set>#include<map>using namespace std; typedef long long ll;typedef unsigned long long ull;#define INF 2023456789#define FOR(i,a,b) for(int i = a; i < b; ++i)#define FORD(i,a,b) for(int i = a; i >= b; --i)#define REP(i,a,b) for(int i = a; i <= b; ++i)#define tr(container, it) \      for(typeof(container.begin()) it = container.begin(); it != container.end(); it++) stack<char> st;char x;int n;int main() {    freopen("in.txt", "r", stdin);    //freopen("out.txt", "w", stdout);    scanf("%d",&n);    scanf("%c",&x);    FOR(i,0,n){        scanf("%c",&x);        if(x == '(') st.push(x);        else { // x = ')'            if(st.empty()){                cout << "false";                return 0;            }            else {                st.pop();            }        }    }    if(st.empty())cout << "true";    else cout << "false";}

input :

7
((()())

output :

false

[beautifulsoul84hung]

Ối bài này đơn giản thôi. Mọi người làm phức tạp quá. tiendaotd thì cho nhiều thư viện làm mình hoa cả mắt ><. Cái gì ko cần đến thì cho vào làm gì hix
Giống như chỉ ăn có 1 bát cơm nhưng lại cho cả một xe ô tô chở bát ra

#include <iostream>using namespace std; int kt (char arr[], int n){    int count = 0;    if (arr[0]!= '(')        return 0;    for (int i = 0; i < n; i ++)    {         if (arr[i] == '(')            count ++;        else            count --;        if (count < 0)            return 0;    }    if (count == 0)        return 1;    else        return 0;} int main (){    int n;    char arr [10];    cout << "Nhap n: ";    cin >> n;     if (n%2 != 0)        cout << "Khong thoa man: " << endl;    else    {        cout << "Nhap (or): ";        cin.ignore (1);        cin.getline (arr, n);        if (kt (arr, n) != 0)            cout << "Thoa man" << endl;        else            cout << "Khong thoa man" << endl;    }    return 0;}

[tiendaotd]

code thằng vào cái template nên nó vậy. Chắc bạn ít code trên online judge nên nhìn ko quen.

@hung : ko biết file input của bạn định dạng thế nào. Nếu theo định dạng

6
((()))

thì phải sửa đoạn

cin.getline (arr, n);

thành

cin.getline (arr, n+1);

mới in ra xâu đúng

 cout << "xau : " << arr << endl;

[beautifulsoul84hung]

code thằng vào cái template nên nó vậy. Chắc bạn ít code trên online judge nên nhìn ko quen.

@hung : ko biết file input của bạn định dạng thế nào. Nếu theo định dạng

6
((()))

thì phải sửa đoạn

cin.getline (arr, n);

thành

cin.getline (arr, n+1);

mới in ra xâu đúng

 cout << "xau : " << arr << endl;

Mình chưa code onl lần nào chỉ code trên IDE. Dữ liệu của mình nhập từ bàn phím
Đã test lại chưa thấy lỗi sai. Còn nếu sửa thành n+1 thì của mình mới có lỗi