avaliador_logico.cpp

/* Avaliador de expressões lógicas
 *
 * Operadores:
 *    ¬  = ! (negação)
 *   /\  = ^ (e)
 *   \/  = | (ou)
 *   ->  = > (condicional)
 *   <-> = - (bicondicional)
 *
 * O fluxo das operações dentro do programa é:
 *   expr -> avaliador -> pseudo codigo -> interpretador -> resultado.
 *
 * A classe opcode_stream é o nosso "compilador", emitimos função de modo linear,
 * por exemplo, se temos que fazer a operação lógica E entre duas proposições p e q
 * fazemos assim:
 *   emitimos a função VAR com o valor de p
 *   emitimos a função VAR com o valor de q
 *   emitimos a função AND
 * Emitimos os parametros antes da operação pois a operação funciona em uma pilha,
 * quando AND for executada, ela pegara da pilha os dois últimos valores e fará
 * a operação lógica, esses dois valores recebidos da pilha sairam, e entrará só o valor
 * do resultado da operação.
 * Ainda existem alguns erros no programa em relação a tolerância a erros na expressão
 * escrita pelo usuário.
 *
 * Marcos Medeiros
 */
#include <iostream>
#include <cstdlib>
#include <cctype>
#include <list>
#include <stack>
#include <cmath>
#include <map>
#include <string>
#include <iomanip>
#include <vector>

using namespace std;


int vars[256];
// variáveis utilizadas na expressão
int cache_vars[256];
int nvars = 0;
int nlines = 0;
map<char,int> varpos;


enum OPCODES
{
	OP_NEG = 0, // negative
	OP_AND, // and
	OP_OR, // or
	OP_COND, // conditional
	OP_BCOND, // biconditional
	OP_VAR, // push var
	OP_OPPAR, // open parentheses
	OP_CLPAR, // close parentheses
	OP_EOS, // end of stream
};

const char *op_name[9] = {
	"neg", "and", "or", "cond", "bcond", "var", "open", "close", "eos"
	};


// nosso processador e construtor de expressões
class opcode_stream
{
	struct opcode {
		int id;
		int val;
		opcode(int _id, int _v)
		{
			id = _id;
			val = _v;
		}
	};

	stack<int> pstack;
	list<opcode> stream;

	void dump_stack()
	{
	    // como não temos iterator para stack, então copiamos a stack
	    // e retiramos valor por valor dela.
	    stack<int> tmp(pstack);

	    while (!tmp.empty())
	    {
	        cout << ", " << tmp.top();
	        tmp.pop();
	    }
	    cout << endl;
	}

	public:
		opcode_stream()
		{
		}
		~opcode_stream()
		{
		}
		// limpa a stream de opcodes
		void flush()
		{
            while(!stream.empty())
                stream.pop_back();
		}

		// Mostra as instruções a serem executadas
		void dissambly()
		{
			list<opcode>::iterator i;
			for (i = stream.begin(); i != stream.end(); i++)
			{
				opcode op = *i;
				cout << op_name[op.id];
				// se for variável, então exibimos o nome
				if (op.id == OP_VAR)
                    cout << " " << (char)op.val;
                cout << endl;
			}

		}

		// emissores de funções lógicas na nossa stream
		void emit_and()
		{
			stream.push_back(opcode(OP_AND, 0));
		}
		void emit_or()
		{
			stream.push_back(opcode(OP_OR, 0));
		}
		void emit_cond()
		{
			stream.push_back(opcode(OP_COND, 0));
		}
		void emit_bcond()
		{
			stream.push_back(opcode(OP_BCOND, 0));
		}
		void emit_neg()
		{
			stream.push_back(opcode(OP_NEG, 0));
		}
		void emit_var(char var)
		{
			stream.push_back(opcode(OP_VAR, var));
		}

		// interpretadores de funções na nossa stream
		void do_and()
		{

			int v1 = pstack.top();
			pstack.pop();
			int v2 = pstack.top();
			pstack.pop();

			pstack.push(v1 && v2);
		}

		void do_or()
		{

			int v1 = pstack.top();
			pstack.pop();
			int v2 = pstack.top();
			pstack.pop();

			pstack.push(v1 || v2);
		}

		void do_cond()
		{

			int v1 = pstack.top();
			pstack.pop();
			int v2 = pstack.top();
			pstack.pop();

			if (v1 == 0 && v2 == 1)
				pstack.push(0);
			else
				pstack.push(1);
		}

		void do_bcond()
		{

			int v1 = pstack.top();
			pstack.pop();
			int v2 = pstack.top();
			pstack.pop();

			pstack.push(v1 == v2);
		}

		void do_neg()
		{
			int v1 = pstack.top();
			pstack.pop();

			pstack.push(v1 ? 0 : 1);
		}

		void do_var(char var)
		{
			pstack.push(vars[(int)var]);
		}

		int exec()
		{
			// limpa a pilha de execução
			while (!pstack.empty())
				pstack.pop();

			list<opcode>::iterator i;
			for (i = stream.begin(); i != stream.end(); i++)
			{
				opcode op = *i;

				//cout << "Exec::"<<op_name[op.id]<<endl;

				switch (op.id)
				{
					case OP_NEG:	do_neg();		break;
					case OP_AND:	do_and();		break;
					case OP_VAR:	do_var(op.val);	break;
					case OP_OR:		do_or();		break;
					case OP_COND:	do_cond();		break;
					case OP_BCOND:	do_bcond();		break;
				}
				//dump_stack();
			}
			return pstack.top();
		}
};


opcode_stream opstream;
//-----------------------------------------------------------------------------
// Analisador léxico
//-----------------------------------------------------------------------------

int tokenid = 0;
char *tokenstr;
// identificador da variável, caso tokenid for OP_VAR
int tokenvid = 0;


int tokenget()
{
    while (isspace(*tokenstr))
        tokenstr++;

	if (*tokenstr != '\0')
	{
		switch (*tokenstr)
		{
			case '^': tokenid = OP_AND; break;
			case '|': tokenid = OP_OR; break;
			case '!': tokenid = OP_NEG; break;
			case '>': tokenid = OP_COND; break;
			case '-': tokenid = OP_BCOND; break;
			case '(': tokenid = OP_OPPAR; break;
			case ')': tokenid = OP_CLPAR; break;
			default:
				// uma variável
				if (isalpha(*tokenstr))
				{
					tokenid = OP_VAR;
					tokenvid = (int) *tokenstr;
				} else {
				    // fechamos o programa pra evitar problemas
				    cout << "Operador invalido " << *tokenstr << endl;
					tokenid = OP_EOS;
					exit(1);
				}
				break;
		}
		++tokenstr;
	} else
		tokenid = OP_EOS;
	return tokenid;
}

//-----------------------------------------------------------------------------
// Analisador recurssivo, nosso "compilador"
//-----------------------------------------------------------------------------

int avail_bcond();
int avail_cond();
int avail_or();
int avail_and();
int avail_neg();
int avail_var();
int avail_error = 0;
// número de linhas da tabela verdade
int calc_conditions()
{
	// cálcula o número de condições para nossa expressão
	int uvars = 0;
	for (int i = 0; i < 256; i++)
		if (cache_vars[i])
			uvars++;
	return pow(2, uvars);
}

int avail()
{
	// limpa as variáveis
	nvars = 0;
	for (int i = 0; i < 256; i++)
	{
		cache_vars[i] = 0;
		vars[i] = 0;
	}
	avail_error = 0;

	tokenget();
	if (tokenid == OP_EOS)
	{
	    avail_error++;
	    return 0;
	}
	avail_bcond();
	if (tokenid != OP_EOS)
		cout << "Avaliação não completada!!! " << tokenid << endl;

	nlines = calc_conditions();
	return avail_error;
}

// avalia a operação BICONDICIONAL
int avail_bcond()
{
	avail_cond();
	if (tokenid == OP_BCOND) {
		tokenget();
		avail_bcond();
		opstream.emit_bcond();
	}
	return 0;
}

// avalia a operação CONDICIONAL
int avail_cond()
{
	avail_or();
	if (tokenid == OP_COND) {
		tokenget();
		avail_cond();
		opstream.emit_cond();
	}
	return 0;
}

// avalia a operação OU
int avail_or()
{
	avail_and();
	if (tokenid == OP_OR) {
		tokenget();
		avail_or();
		opstream.emit_or();
	}
	return 0;
}

// avalia a operação E
int avail_and()
{
	avail_neg();
	if (tokenid == OP_AND) {
		tokenget();
		avail_and();
		opstream.emit_and();
	}
	return 0;
}

// avalia a operação de negação
int avail_neg()
{
	if (tokenid == OP_NEG) {
		tokenget();

		if (tokenid == OP_EOS)
		{
		    avail_error++;
		    return 0;
		}
		avail_neg();
		opstream.emit_neg();
	} else avail_var();
	return 0;
}

int avail_var()
{
	if (tokenid == OP_VAR) {
		tokenget();
		// marca a nossa variável na lista das utilizadas
		if (!cache_vars[tokenvid]) {
			varpos[nvars]=tokenvid;
			++nvars;
		}
		cache_vars[tokenvid] = 1;
		opstream.emit_var(tokenvid);
	} else
	// Analisa subexpressões (...)
	if (tokenid == OP_OPPAR) {
		tokenget();
		avail_bcond();
		// quando retornamos a esse ponto, esperamos que o token seja ')'
		// pois nenhuma outra função dentro da recurssão lida com este token
		if (tokenid != OP_CLPAR) {
			cout << "Erro de sintaxe!\n";
			avail_error++;
			return 0;
		} else {
			// recomeçamos a avaliação
		    tokenget();
		}
	}
	return 0;
}




// define os valores das variáveis para avaliar as linhas e executa uma por uma
int execute()
{
	int values[nvars][nlines];
    int result[nlines];
	int max_y = nlines / 2;
	int cond = 1;
    int count = 0;

	for (int v = 0; v < nvars; v++)
	{
		for (int l = 0; l < nlines; l++)
		{
			// verifica se o contador chegou no máximo de vezes que uma
			// condição aparece sucedendo a outra
			if (count == max_y)
			{
				// alterna o valor entre 0 e 1 sempre
				cond ^= 1;
				// recomeça a contar
				count = 0;
			}

			values[v][l] = cond;
			count++;
		}
		// corta pela metade o número de condições que aparecerem juntas
		max_y /= 2;
		// zera o contador
		count = 0;
		// sempre começamos com verdadeiro
		cond = 1;
	}

	// define os valores para a linha
	for (int l = 0; l < nlines; l++)
	{
        cout << setw(3) << (l+1) << " (";
		for (int v = 0; v < nvars; v++)
		{
			vars[varpos[v]] = values[v][l];
			cout << (vars[varpos[v]] ? 'V' : 'F');
			// verifica se não é a última variável
			if ((v + 1) != nvars)
                cout << ",";
		}
		cout << ")";
		result[l] = opstream.exec();
		// exibe o resultado da expressão avaliada na linha
		cout << " = " << (result[l] ? 'V' : 'F') << endl;
	}
	return 0;
}

const char *help_msg =
"               AVALIADOR DE EXPRESSOES LOGICAS\n"
"               Desenvolvido por Marcos Medeiros\n\n"
"Simbolos para operacoes:\n"
"     !   : expressa negacao de uma proposicao,       ex: !p\n"
"     ^   : expressa a condicao logica E,             ex: (p ^ q)\n"
"     |   : expressa a condicao logica OU,            ex: (p | q)\n"
"     >   : expressa a condicao logica CONDICIONAL,   ex: (p > q)\n"
"     -   : expressa a condicao logica BICONDICIONAL, ex: (p - q)\n"
" Digite 'sair' para sair do programa.\n"
" Digite 'ajuda' para exibir esse cabecalho\n";

int main()
{

	cout << help_msg << ">>> ";
    do
    {

        string buffer;
        getline(cin, buffer);
        tokenstr = (char*) buffer.c_str();

        if (buffer == "sair")
            break;
        if (buffer == "ajuda")
        {
            cout << help_msg << endl;
            goto _recomeca;
        }

        opstream.flush();
        avail();
        if (avail_error)
        {
            cout << "Houve erro de avaliacao em \"" << tokenstr << endl;
        }
        else
        {
            cout << "Numero de variaveis: " << nvars << endl;
            cout << "Numero de linhas da tabela verdade: " << nlines << endl;
            opstream.dissambly();
            execute();
        }
    _recomeca:
        cout << ">>> ";
    } while (1);

	return 0;
}