Hoje uma nova seção no Lab C++. As sextas-feiras serão reservadas para solução de exercícios e problemas encontrados em provas, cursos técnicos, superior, concursos, entrevistas de emprego, etc. Esta seção é voltada para tirar dúvidas dos leitores, portanto envie suas dúvidas, suas sugestões. Todas vão entrar na fila, serão resolvidas e publicadas na sequência.

A solução de hoje um problema ao qual fui submetido recentemente. Um avaliador pediu pra eu fazer um programa que validasse a abertura e fechamento de parênteses, colchetes e chaves.

Como Não Resolver

Meu primeiro impulso foi fazer três contadores, um contador de parênteses, um de colchetes e um de chaves, incrementando quando encontrasse uma abertura, e decrementando quando encontrasse um fechamento. Isso não funciona porque se houver um cruzamento de abertura e fechamento não vai ser detectado, como no caso a seguir:

x = a[0] * (a[1] + a[2)];

Solução

A solução, então, tem que ser implementada utilizando uma pilha, aí sim é possível ter certeza que vamos contar certinho. A solução vai ficar mais ou menos assim:

#include <iostream>
#include <map>
#include <stack>
#include <sstream>
int main() {
    std::stringstream ss;
    std::stack<char> check;
    std::map<char, char> close;
    close['('] = ')'; close['['] = ']'; close['{'] = '}';
    ss.str("x = a[0] * (a[1] + a[2)];");
    while (!ss.eof()) {
        char c;
        char top;
        ss >> c;
        switch (c) {
            case '(':
            case '[':
            case '{':
                check.push(c);
                break;
            case ')':
            case ']':
            case '}':
                if (!check.empty() && c == close[check.top()]) {
                    check.pop();
                } else {
                    std::cout << "error on position " << ss.tellg() << std::endl;
                    exit(1);
                }
                break;
        }
    }
}

Cada abertura de parênteses, colchetes ou chaves encontradas adiciona-se uma cópia na pilha. Quando encontramos o fechamento verificamos se é correspondente à abertura que está no topo da pilha, sendo correspondente basta retirar da pilha, se não for houve um erro.

O std::map close mapeia o fechamento de cada elemento, isso facilita quando for detectar se o fechamento do fechamento corresponde à abertura que está na pilha.

O código utiliza um std::stringstream para poder ser facilmente convertido para utilizar std::cin, ou por um std::ifstream, assim o algoritmo fica bem mais fácil de ser reaproveitado.

Extendendo o Problema

Para extender o problema vamos propor adicionar suporte a aspas, só que vamos considerar ser possível colocar parênteses, colchetes e chaves dentro das aspas, e nesse caso devem ser ignorados:

#include <iostream>
#include <map>
#include <stack>
#include <sstream>
int main() {
    std::stringstream ss;
    std::stack<char> check;
    std::map<char, char> close;
    bool squote = false, dquote = false;
    close['('] = ')'; close['['] = ']'; close['{'] = '}';
    ss.str("x = a[0] * (a[1] + a['2)']);");
    while (!ss.eof()) {
        char c;
        char top;
        ss >> c;
        if (
(squote && c == '\'') ||
 (dquote && c == '"')
) {
            dquote = squote = false;
            continue;
        }
        if (squote || dquote)
            continue;
        switch (c) {
            case '\'':
                squote = true;
                break;
            case '"':
                dquote = true;
                break;
            case '(':
            case '[':
            case '{':
                check.push(c);
                break;

            case ')':
            case ']':
            case '}':
                if (!check.empty() && c == close[check.top()]) {
                    check.pop();
                } else {
                    std::cout << "error on position " << ss.tellg() << std::endl;
                    exit(1);
                }
                break;
        }
    }
}

No exemplo acima quando encontramos aspas, simples ou duplas, o switch-case é suspenso, e só volta a ser executado quando encontramos o fechamento das aspas.

Proposta de Melhoria

Agora o desafio pra ficar mais legal. E se dentro das aspas simples, ou duplas, houver um escape de aspas? Eis o desafio, suporte a escape de aspas dentro das aspas. Será que você consegue fazer?

Tags: c++, estruturas de dados