Algorithm


Problem Name: 2 AD-HOC - beecrowd | 2406

Problem Link: https://www.beecrowd.com.br/judge/en/problems/view/2406

Expressões

 

Por OBI - Olimpíada Brasileira de Informática 2011 BR Brazil

Timelimit: 1

Pedrinho e Zezinho estão precisando estudar resolução de expressões matemáticas para uma prova que irão fazer. Para isso, eles querem resolver muitos exercícios antes da prova. Como sabem programar, então decidiram fazer um gerador de expressões matemáticas.

O gerador de expressões que eles criaram funciona em duas fases. Na primeira fase é gerada uma cadeia de caracteres que contém apenas os caracteres '{', '[', '(', '}', ']' e ')'. Na segunda fase, o gerador adiciona os números e operadores na estrutura criada na primeira fase. Uma cadeia de caracteres é dita bem definida (ou válida) se atende as seguintes propriedades:

  1. Ela é uma cadeia de caracteres vazia (não contém nenhum caractere).
  2. Ela é formada por uma cadeia bem definida envolvida por parênteses, colchetes ou chaves. Portanto, se a cadeia S é bem definida, então as cadeias (S), [S] e {S} também são bem definidas.
  3. Ela é formada pela concatenação de duas cadeias bem definidas. Logo, se as cadeias X e Y são bem definidas, a cadeia XY é bem definida.

Depois que Pedrinho e Zezinho geraram algumas expressões matemáticas, eles perceberam que havia algum erro na primeira fase do gerador. Algumas cadeias não eram bem definidas. Eles querem começar a resolver as expressões o mais rápido possível, e sabendo que você é um ótimo programador (e participa da OBI) resolveram pedir que escreva um programa que dadas várias cadeias geradas na primeira fase, determine quais delas são bem definidas e quais não são.

 

Entrada

 

A entrada é composta por diversas instâncias. A primeira linha da entrada contém um inteiro T (1 ≤ T ≤ 20) indicando o número de instâncias. Em seguida temos T linhas, cada uma com uma cadeia A, (a cadeia de caracteres A tem entre 1 e 100000 caracteres), (a cadeia de caracteres A contém apenas caracteres '{', '[', '(', '}', ']' e ')' ).

 

Saída

 

Para cada instância imprima uma linha contendo a letra S se a cadeia é bem definida, ou a letra N caso contrário.

 

 

 

Exemplo de Entrada Exemplo de Saída

12

()

[]

{}

(]

}{

([{}])

{}()[]

()]

{[]

(

(([{}{}()[]])(){}){}

(((((((((({([])}])))))))))

S

S

S

N

N

S

S

N

N

N

S

N

 

Code Examples

#1 Code Example with C Programming

Code - C Programming


#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define true 1
#define false 0
#define MAXSIZE 100100

typedef struct tipoNo{

	char caractere;
	struct tipoNo *proximo;

} tipoNo;

typedef struct tipoPilha{

	tipoNo *topo;

} tipoPilha;

void pop(tipoPilha *);
char top(tipoPilha *);
void stack(tipoPilha *);
_Bool empty(tipoPilha *);
void push(tipoPilha *, char );

int main (void)
{

	int n;
	unsigned i, caso;
	_Bool flag;
	char string[MAXSIZE];

	scanf("%d", &n);

	caso = 0;
	while (n--)
	{

		// memset(string, 0, sizeof(string));
		scanf("%s", string);

		// printf("%u) String: %s\n\n", ++caso, string);

		flag = true;
		tipoPilha pilha;
		stack(&pilha);

		for (i = 0; string[i]; ++i)
		{

			if (string[i] == '{' || string[i] == '[' || string[i] == '(')
				push(&pilha, string[i]);
			else
			{

				if (empty(&pilha))
				{

					flag = false;
					break;

				}

				// printf("%c\n", top(&pilha));

				if (string[i] == '}' && top(&pilha) == '{')
					pop(&pilha);
				else if (string[i] == ']' && top(&pilha) == '[')
					pop(&pilha);
				else if (string[i] == ')' && top(&pilha) == '(')
					pop(&pilha);
				else
				{

					flag = false;
					break;

				}

			}

		}

		if (!empty(&pilha))
			flag = false;

		printf("%s\n", flag ? "S" : "N");

	}

}

void stack(tipoPilha *pilha)
{

	pilha->topo = NULL;

}

void push(tipoPilha *pilha, char caractere)
{

	tipoNo *auxiliar;
	auxiliar = (tipoNo *) malloc(sizeof(tipoNo));

	if (!auxiliar)
		exit(1);

	auxiliar->proximo = pilha->topo;
	pilha->topo = auxiliar;
	auxiliar->caractere = caractere;

}

void pop(tipoPilha *pilha)
{

	tipoNo *auxiliar;
	auxiliar = pilha->topo;

	if (auxiliar)
	{

		pilha->topo = auxiliar->proximo;
		free(auxiliar);

	}

}

char top(tipoPilha* pilha)
{

	return pilha->topo->caractere;

}

_Bool empty(tipoPilha *pilha)
{

	return pilha->topo == NULL;

}
Copy The Code & Try With Live Editor

Input

x
+
cmd
12
()
[]
{}
(]
}{
([{}])
{}()[]
()]
{[]
(
(([{}{}()[]])(){}){}
(((((((((({([])}])))))))))

Output

x
+
cmd
S
S
S
N
N
S
S
N
N
N
S
N

#2 Code Example with C++ Programming

Code - C++ Programming


#include <cstdio>
#include <cstring>
#define MAX 100010
int tam, n, i, j, tamanho;
char pilha[MAX], entrada[MAX];
void clear() { tam = 0; }
void push(char x) { pilha[++tam] = x; }
void pop() {
    if (tam > 0) tam--;
}
char top() { return pilha[tam]; }
int main() {
    scanf("%d", &n);
    for (i = 0; i  <  n; i++) {
        clear();
        scanf("%s", entrada);
        tamanho = strlen(entrada);
        bool verdade = true;
        for (j = 0; j  <  tamanho; j++) {
            if (entrada[j] == '(')
                push('(');
            else if (entrada[j] == '[')
                push('[');
            else if (entrada[j] == '{')
                push('{');
            else if (entrada[j] == ')') {
                if (top() == '(')
                    pop();
                else {
                    verdade = false;
                    break;
                }
            } else if (entrada[j] == ']') {
                if (top() == '[')
                    pop();
                else {
                    verdade = false;
                    break;
                }
            } else if (entrada[j] == '}') {
                if (top() == '{')
                    pop();
                else {
                    verdade = false;
                    break;
                }
            }
        }
        if (verdade && tam == 0)
            printf("S\n");
        else
            printf("N\n");
    }
    return 0;
}
Copy The Code & Try With Live Editor

Input

x
+
cmd
12
()
[]
{}
(]
}{
([{}])
{}()[]
()]
{[]
(
(([{}{}()[]])(){}){}
(((((((((({([])}])))))))))

Output

x
+
cmd
S
S
S
N
N
S
S
N
N
N
S
N
Advertisements

Demonstration


Previous
#2405 Beecrowd Online Judge Solution 2405 Colorindo Solution in C, C++, Java, Js and Python
Next
#2407 Beecrowd Online Judge Solution 2407 Quadrado Mágico Solution in C, C++, Java, Js and Python