Submit | All submissions | Best solutions | Back to list |
EDUPT12 - Expressões |
O pessoal de Cálculo 1 está sofrendo para se preparar para a primeira avaliação, é uma revisão do ensino médio, mas mesmo assim a dificuldade tem sido sentida. Como aprenderam recentemente a programar, então decidiram fazer um gerador de expressões matemáticas, para ampliar a quantidade de exercícios disponíveis para resolução.
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 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 veterano e ótimo programador 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.
Sua professora de ED, gente boa toda vida, te deu a ideia de usar pilhas para resolver o problema e ainda disponibilizou o código de pilha implementado em C, que você vai usar com certeza.
Então mãos à obra.
Entrada
A entrada é composta por diversas instâncias. A primeira linha da entrada contém um inteiro T indicando o número de instâncias. Em seguida temos T linhas, cada uma com uma cadeia A.
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.
Restrições
- 1 ≤ T ≤ 20.
- a cadeia de caracteres A tem entre 1 e 100000 caracteres.
- a cadeia de caracteres A contém apenas caracteres '{', '[', '(', '}', ']' e ')'.
Exemplos
Entrada 12 () [] {} (] }{ ([{}]) {}()[] ()] {[] ( (([{}{}()[]])(){}){} (((((((((({([])}]))))))))) Saída S S S N N S S N N N S N
Added by: | IFTM_Maratona |
Date: | 2022-11-10 |
Time limit: | 10s-200s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | C |