Descrição do Problema

A linguagem LISP utiliza uma sintaxe baseada exclusivamente no pareamento de parênteses, seguindo o formato (OP P1 P2 ...), onde os elementos são separados por espaços. O primeiro elemento, OP, representa o operador, e os elementos subsequentes são seus operandos.

Neste desafio, os operadores suportados são add (adição), sub (subtração), mul (multiplicação) e div (divisão inteira). Cada operação recebe exatamente dois operandos, que podem ser números inteiros ou outras expressões aninhadas.

Regras de Entrada e Saída

• Entrada: Uma string de até 512 caracteres repersentando a expressão, garantida como sintaticametne válida.
• Saída: O resultado numérico da avaliação ou a string "error" caso ocorra uma divisão por zero.

Exemplos

Estratégia de Resolução

Em vez de utilizar múltiplas pilhas e controle complexo de índices, podemos simplificar a lógica empregando uma única pilha de avaliação. A abordagem percorre a string caractere por caractere:

1. Ignoramos os parênteses de abertura ( e os espaços.
2. Ao identificar uma sequência de letras, extraímos o operador (add, sub, mul, div) e o empilhamos.
3. Ao identificar um número (incluindo o sinal de negativo), convertemos para inteiro e o empilhamos.
4. Ao encontrar um parêntese de fechamento ), desempilhamos o segundo operando, o primeiro operando e o operador. Realizamos o cálculo e empilhamos o resultado parcial.
5. Ao final do processamento, o único elemento restante na pilha será o resultado final.

Implementação em Python

def avaliar_expressao_lisp(expressao: str) -> str:
    pilha = []
    i = 0
    n = len(expressao)
    
    while i < n:
        caractere = expressao[i]
        
        if caractere == '(' or caractere == ' ':
            i += 1
            continue
            
        if caractere == ')':
            operando_b = pilha.pop()
            operando_a = pilha.pop()
            operador = pilha.pop()
            
            if operador == 'add':
                pilha.append(operando_a + operando_b)
            elif operador == 'sub':
                pilha.append(operando_a - operando_b)
            elif operador == 'mul':
                pilha.append(operando_a * operando_b)
            elif operador == 'div':
                if operando_b == 0:
                    return "error"
                pilha.append(operando_a // operando_b)
            i += 1
            continue
            
        if caractere.isalpha():
            j = i
            while j < n and expressao[j].isalpha():
                j += 1
            pilha.append(expressao[i:j])
            i = j
            continue
            
        if caractere.isdigit() or caractere == '-':
            j = i
            if caractere == '-':
                j += 1
            while j < n and expressao[j].isdigit():
                j += 1
            pilha.append(int(expressao[i:j]))
            i = j
            continue
            
        i += 1
        
    return str(pilha[0]) if pilha else "error"

if __name__ == "__main__":
    casos = [
        "(mul 3 -7)",
        "(add 1 2)",
        "(sub (mul 2 4) (div 9 3))",
        "(div 10 0)"
    ]
    for caso in casos:
        print(f"Entrada: {caso} -> Saida: {avaliar_expressao_lisp(caso)}")

Implementação em JavaScript

function processarLisp(texto) {
    const pilha = [];
    let indice = 0;
    const tamanho = texto.length;
    
    while (indice < tamanho) {
        const char = texto[indice];
        
        if (char === '(' || char === ' ') {
            indice++;
            continue;
        }
        
        if (char === ')') {
            const val2 = pilha.pop();
            const val1 = pilha.pop();
            const op = pilha.pop();
            
            switch (op) {
                case 'add': pilha.push(val1 + val2); break;
                case 'sub': pilha.push(val1 - val2); break;
                case 'mul': pilha.push(val1 * val2); break;
                case 'div':
                    if (val2 === 0) return "error";
                    pilha.push(Math.trunc(val1 / val2));
                    break;
            }
            indice++;
            continue;
        }
        
        if (/[a-z]/.test(char)) {
            let fim = indice;
            while (fim < tamanho && /[a-z]/.test(texto[fim])) fim++;
            pilha.push(texto.substring(indice, fim));
            indice = fim;
            continue;
        }
        
        if (/\d|-/.test(char)) {
            let fim = indice;
            if (char === '-') fim++;
            while (fim < tamanho && /\d/.test(texto[fim])) fim++;
            pilha.push(parseInt(texto.substring(indice, fim), 10));
            indice = fim;
            continue;
        }
        
        indice++;
    }
    
    return pilha.length > 0 ? String(pilha[0]) : "error";
}

const testes = [
    "(mul 3 -7)",
    "(add 1 2)",
    "(sub (mul 2 4) (div 9 3))",
    "(div 10 0)"
];

testes.forEach(t => console.log(`Entrada: ${t} -> Saida: ${processarLisp(t)}`));

Implementação em C

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

#define MAX_TAM 1024

typedef struct {
    char dados[MAX_TAM][20];
    int topo;
} PilhaStr;

void push_str(PilhaStr *p, const char *s) {
    strcpy(p->dados[p->topo++], s);
}

char* pop_str(PilhaStr *p) {
    return p->dados[--p->topo];
}

char* avaliar_lisp_c(const char *expr) {
    PilhaStr pilha;
    pilha.topo = 0;
    int i = 0;
    int len = strlen(expr);
    static char resultado[20];
    
    while (i < len) {
        if (expr[i] == '(' || expr[i] == ' ') {
            i++;
            continue;
        }
        if (expr[i] == ')') {
            int b = atoi(pop_str(&pilha));
            int a = atoi(pop_str(&pilha));
            char *op = pop_str(&pilha);
            int res = 0;
            
            if (strcmp(op, "add") == 0) res = a + b;
            else if (strcmp(op, "sub") == 0) res = a - b;
            else if (strcmp(op, "mul") == 0) res = a * b;
            else if (strcmp(op, "div") == 0) {
                if (b == 0) return "error";
                res = a / b;
            }
            sprintf(resultado, "%d", res);
            push_str(&pilha, resultado);
            i++;
            continue;
        }
        if (isalpha(expr[i])) {
            char op[4] = {0};
            int j = 0;
            while (i < len && isalpha(expr[i])) {
                op[j++] = expr[i++];
            }
            push_str(&pilha, op);
            continue;
        }
        if (isdigit(expr[i]) || expr[i] == '-') {
            char num[20] = {0};
            int j = 0;
            if (expr[i] == '-') num[j++] = expr[i++];
            while (i < len && isdigit(expr[i])) {
                num[j++] = expr[i++];
            }
            push_str(&pilha, num);
            continue;
        }
        i++;
    }
    return pop_str(&pilha);
}

int main() {
    const char *testes[] = {
        "(mul 3 -7)",
        "(add 1 2)",
        "(sub (mul 2 4) (div 9 3))",
        "(div 10 0)"
    };
    for (int i = 0; i < 4; i++) {
        printf("Entrada: %s -> Saida: %s\n", testes[i], avaliar_lisp_c(testes[i]));
    }
    return 0;
}
</ctype.h></string.h></stdlib.h></stdio.h>

Implementação em C++

#include <iostream>
#include <string>
#include <stack>
#include <cctype>

using namespace std;

string calcularExpressao(const string& texto) {
    stack<string> pilha;
    int i = 0;
    int n = texto.length();
    
    while (i < n) {
        char c = texto[i];
        
        if (c == '(' || c == ' ') {
            i++;
            continue;
        }
        
        if (c == ')') {
            int val2 = stoi(pilha.top()); pilha.pop();
            int val1 = stoi(pilha.top()); pilha.pop();
            string op = pilha.top(); pilha.pop();
            
            int res = 0;
            if (op == "add") res = val1 + val2;
            else if (op == "sub") res = val1 - val2;
            else if (op == "mul") res = val1 * val2;
            else if (op == "div") {
                if (val2 == 0) return "error";
                res = val1 / val2;
            }
            pilha.push(to_string(res));
            i++;
            continue;
        }
        
        if (isalpha(c)) {
            string op = "";
            while (i < n && isalpha(texto[i])) {
                op += texto[i++];
            }
            pilha.push(op);
            continue;
        }
        
        if (isdigit(c) || c == '-') {
            string num = "";
            if (c == '-') num += texto[i++];
            while (i < n && isdigit(texto[i])) {
                num += texto[i++];
            }
            pilha.push(num);
            continue;
        }
        
        i++;
    }
    
    return pilha.empty() ? "error" : pilha.top();
}

int main() {
    string casos[] = {
        "(mul 3 -7)",
        "(add 1 2)",
        "(sub (mul 2 4) (div 9 3))",
        "(div 10 0)"
    };
    
    for (const string& caso : casos) {
        cout << "Entrada: " << caso << " -> Saida: " << calcularExpressao(caso) << "\n";
    }
    
    return 0;
}
</string></cctype></stack></string></iostream>