1068 - Balanço de Parênteses I

Ainda temos algumas alternativas sem usar estruturas de dados sofisticadas...

Descrição

beecrowd Talent Cloudbeecrowd

Solução

Como estamos lidando com apenas um tipo de símbolo, o parênteses, então esse problema é um pouco mais simples do que outras variações do mesmo. A alternativa 1 é extremamente parecida com a alternativa 2 do problema 1245 - Botas Perdidas e a alternativa 2 utiliza-se de uma pilha para guardar quantos parênteses já lemos até então.

Ambas as alternativas seguem o mesmo raciocínio de que quando vemos um parênteses fechado, precisamos avaliar se há algum parênteses aberto anteriormente que pode ser usado como par para esse parênteses fechado. Outro detalhe importante é que ao final da expressão, devemos também ver se não há parênteses abertos sobrando.

Alternativa 1 - Acumulando a soma dos parênteses

C99

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

int main(){
    char expressao[1001];
    int i, tam, parenteses;

    while(scanf("%s\n", &expressao) != EOF){
        parenteses = 0;
        tam = strlen(expressao);

        for(i = 0; i < tam; ++i){
            if(expressao[i] == '('){
                ++parenteses;
            }else if(expressao[i] == ')'){
                if(parenteses > 0)  --parenteses;
                else                break;
            }
        }

        if(i == tam && parenteses == 0) printf("correct\n");
        else                            printf("incorrect\n");
    }

    return 0;
}

C++17

JavaScript 12.18

Python 3.9

Alternativa 2 - Usando pilha

C99

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

struct pilhaNo{
    char valor;
    struct pilhaNo* abaixo;
};

struct pilha{
    int tamanho;
    struct pilhaNo* topo;
};

void push(struct pilha* p, int valor){
    p->tamanho += 1;
    struct pilhaNo* novoTopo = (struct pilhaNo*) malloc(sizeof(struct pilhaNo));

    novoTopo->valor = valor;
    novoTopo->abaixo = p->topo;
    p->topo = novoTopo;
}

void pop(struct pilha* p){
    if(p->tamanho > 0){
        p->tamanho -= 1;
        struct pilhaNo* velhoTopo = p->topo;
        p->topo = p->topo->abaixo;
        free(velhoTopo);
    }
}

char top(struct pilha* p){
    return p->topo->valor;
}

int size(struct pilha* p){
    return p->tamanho;
}

int empty(struct pilha* p){
    return p->tamanho == 0;
}

void inicializa(struct pilha* p){
    p->tamanho = 0;
    p->topo = NULL;
}

void destroi(struct pilha* p){
    while(!empty(p)){
        pop(p);
    }
}

int main(){
    int i, tam;
    struct pilha p;
    char expressao[1001];

    while(scanf("%s\n", &expressao) != EOF){
        inicializa(&p);
        tam = strlen(expressao);

        for(i = 0; i < tam; ++i){
            if(expressao[i] == '('){
                push(&p, '(');
            }else if(expressao[i] == ')'){
                if(empty(&p))   break;
                else            pop(&p);
            }
        }

        if(i == tam && empty(&p))   printf("correct\n");
        else                        printf("incorrect\n");

        destroi(&p);
    }

    return 0;
}

C++17

JavaScript 12.18

Python 3.9