#include "stdafx.h"
#include "stdio.h"
#include <string>
#include <iostream>
#include <stdlib.h>
#include <conio.h>
#include <cstringt.h>
#define nn 10

struct code_op         //структура для хранения допустимых символов операций
{
	char   symbol;      //символ
	char   priority;   //приоритет операции
};
//коды операций, как индекс в массиве codes
#define SPACE_CODE   0
#define OR_CODE      1
#define AND_CODE   2
#define NOT_CODE   3
#define XOR_CODE   4
#define IMP_CODE   5
#define EQU_CODE   6
#define OPEN_CODE   7
#define CLOSE_CODE   8
#define MAX_CODE   9
code_op   codes[MAX_CODE] =
{
	{ ' ', 0 },         //разделитель (игнорируется)
	{ '|', 2 },         //или
	{ '&', 3 },         //и
	{ '~', 7 },         //отрицание
	{ '+', 4 },         //исключающее или
	{ '>', 5 },         //импликация
	{ '=', 6 },         //эквиваленция
	{ '(', 1 },         //открывающая скобка
	{ ')', 1 }         //закрывающая скобка
};
int CmpOp(char op)      //поиск кода в массиве codes
{
	int      i;
	for (i = 0; i<MAX_CODE; i++)
	{
		if (codes[i].symbol == op)
			return i;   //возвращаем индекс
	}
	return -1;         //или -1, если не найдено
}
//построение обратной польской нотации с проверкой на корректность.
//параметры:
//str - входная строка с обычной нотацией
//opn - выходная строка с обратной польской нотацией
//возвращается количество переменных или -1, если любая ошибка
int OPN(char *str, char *opn)
{
	char   *temp = opn;   //сохраним адрес выхожной строки для окончательной проверки
	char   stack[nn];      //стек, растет снизу вверх
	int      top = 0;      //вершина стека
	int      cnt = 0;      //количество аргументов
	int      check;         //переменная для последней проверки корректности
	char   code;         //текущий символ
	for (code = *(str++); code; code = *(str++))   //по всем символам строки
	{
		if ((code >= 'A') && (code <= 'Z'))   //заглавные буковки переменных
			code += 0x20;               //превратим в малые!
		if ((code >= 'a') && (code <= 'z'))   //переменные ?
		{
			*(opn++) = code;            //пишем в выходную строку
			if (cnt < (code - 'a' + 1))         //одновременно ищем количество переменных,
				cnt = code - 'a' + 1;         // как максимальный используемый код
			while (top && (stack[top - 1] == NOT_CODE))   //если перед этим было отрицание
				*(opn++) = stack[--top];   //извлечем из стека в выходную строку
		}
		/*else if ((code == '1')||(code == '0'))   //явные константы
		{
		*(opn++) = code;               //пишем в строку, как переменные
		while (top && (stack[top-1] == NOT_CODE))   //если перед этим было отрицание
		*(opn++) = stack[--top];   //извлечем из стека в выходную строку
		}*/
		else
		{
			code = CmpOp(code);            //проверим на допустимый код операции, возвращается индекс в массиве
			if (code == SPACE_CODE)
				continue;               //пробелы игнорируем
			else
			{
				if (code == OPEN_CODE)      //открывающая скобка?
					stack[top++] = code;   //пишем в стек
				else if (code == CLOSE_CODE)//закрывающая скобка?
				{
					if (top)            //есть что-то в стеке?
					{
						for (code = stack[--top]; code != OPEN_CODE; code = stack[--top])
						{               //пока не дойдем до открывающей скобки
							*(opn++) = code;//извлекаем код операции в выходную строку
							if (top == 0)   //проверим на парность скобок
								return -1;   //если дошли до 0, значит открывающей скобки не было, ошибка!
						}
						while (top && (stack[top - 1] == NOT_CODE))   //извлечем из стека отрицания,
							*(opn++) = stack[--top];            // которые перед открывающей скобкой
					}
					else
						return -1;         //в стеке ничего нет - ошибка!
				}
				else                  //код операции
				{                     //проверим приоритет операций
					if (top != 0)         //в случае, если что-то есть в стеке
					{
						if (stack[top - 1] != NOT_CODE)   //кроме отрицания!
														  //если приоритет новой операции меньше или равен
														  //приоритета операции в стеке
							if (codes[code].priority <= codes[stack[top - 1]].priority)
								*(opn++) = stack[--top];   //то извлечем код операции из стека
					}
					stack[top++] = code;   //запишем новый код в стек
				}
			}
		}
	}
	//извлечем из стека операции
	while (top)                        //пока что-то там есть
	{
		if (stack[top - 1] != OPEN_CODE)      //но никак не открывающая скобка!
			*(opn++) = stack[--top];
		else
			return -1;                  //( - ошибка!
	}
	*opn = 0;                        //закроем строку нулем
									 //проверим строку на соответствие операций и переменных!
									 //чтобы у операций (кроме отрицания) было два аргумента!
	check = 0;                        //счетчик аргументов
	for (code = *(temp++); code; code = *(temp++))//по всем символам opn
	{
		if (code < MAX_CODE)            //операция?
		{
			if (code != NOT_CODE)         //не отрицание, для него надо один аргумент
			{
				check--;               //операции из двух аргументов получают один, т.е. уменьшаем на 1
			}
		}
		else
			check++;                  //для аргументов увеличиваем на 1
	}
	if (check != 1)                     //в итоге должны получить 1! Последний аргумент и будет результатом
		return -1;                     //иначе - ошибка!
	return cnt;                        //возвращаем количество переменных
}
void print_opn(char *opn)               //вывод строки ОПН
{
	char   ch;
	printf("OPN = ");
	for (ch = *(opn++); ch; ch = *(opn++))      //по всем символам строки
	{
		if (ch >= 'a')                  //переменную
			printf("%c", ch);            //выводим, как ее саму
		else
			printf("%c", codes[ch].symbol);   //операцию, как символ из массива (в строке ОПН лежит индекс)
	}
	printf("\n");
}
void print_header(int cnt)               //заголовок таблицы истинности, параметр - число переменных
{
	int      i;

	for (i = 0; i<cnt; i++)               //для всех
		printf("%c ", i + 'a');            //выводим буковки, разделяя пробелом
	printf("f\n");                     //f, как идентификатор значения функции
}
//расчет функции для конкретного набора значений переменных
//значения задаются битами в параметре row, которые можно рассматривать, как номер строки
//параметры:
// opn - строка обратной польской нотации
// row - порядковый номер строки
// cnt - количество переменных
//возвращает значение функции на конкретном наборе переменных
int F(char* opn, int row, int cnt)
{
	char res(0);
	bool first(false), chet(false);
	char   stack[nn];      //стек для отработки ОПН
	int      top = 0;      //вершина стека, растет вверх
	char   ch;
	for (ch = *(opn++); ch; ch = *(opn++))   //по всем символам ОПН
	{
		if (ch >= 'a')               //переменная?
									 //пишем в стек значение соответствующего бита в row
									 //номер переменной (0,1,...) получаем, как ch-'a'
									 //из-за того, что младший бит справа,
									 //перевернем номер относительно количества переменных
									 //т.е. получим cnt-ch+'a'-1
									 //тогда маска бита получается 1<<(cnt-ch+'a'-1)
									 //в стек получим или 1, или 0, как результат сравнения не 0
			stack[top++] = (char)(((1 << (cnt - ch + 'a' - 1)) & row) != 0);
		else
			switch (ch)               //для операций
			{                     //берем два значения (или одно для отрицания) из стека,
								  // делаем операцию и отправляем обратно в стек
			case OR_CODE:
				for (int i(top - 1); i >= 0; --i)
					if ((stack[i] == 1) || (stack[i] == 0))
						if (!first) {
							res = stack[i];
							first = true;
						}
						else
							res |= stack[i];
				//stack[top++] = stack[--top] | stack[--top];   //или
				break;
			case AND_CODE:
				for (int i(top - 1); i >= 0; --i)
					if ((stack[i] == 1) || (stack[i] == 0))
						if (!first) {
							res = stack[i];
							first = true;
						}
						else
							res &= stack[i];
				//stack[top] = stack[top-1] & stack[top-2];   //и
				break;
			case NOT_CODE:
				for (int i(top - 1); i >= 0; --i)
					if ((stack[i] == 1) || (stack[i] == 0))
						if (!first) {
							res = 1 ^ stack[i];
							first = true;
						}
						else
							res = 1 ^ stack[i];
				//stack[top++] = 1 ^ stack[--top];         //отрицание, как исключающее или с 1
				break;
			case XOR_CODE:
				for (int i(top - 1); i >= 0; --i)
					if ((stack[i] == 1) || (stack[i] == 0))
						if (!first) {
							res = stack[i];
							first = true;
						}
						else
							res ^= stack[i];
				//stack[top++] = stack[--top] ^ stack[--top];   //исключающее или
				break;
			case IMP_CODE:
				for (int i(top - 1); i >= 0; --i)
					if ((stack[i] == 1) || (stack[i] == 0))
						if (!first) {
							res = stack[i];
							first = true;
						}
						else
							if (chet) {
								res |= stack[i];
								chet = false;
							}
							else {
								res |= (1 ^ stack[i]);
								chet = true;
							}
							//stack[top++] = stack[--top] | (1 ^ stack[--top]);   //импликация по формуле a->b=~a|b
							break;                                    //сначала достаем второй аргумент!
			case EQU_CODE:
				stack[top++] = 1 ^ (stack[--top] ^ stack[--top]);   //эквиваленция, как отрицание xor
				break;
			}
	}
	return res;//stack[top];            //после всех расчетов в вершине стека - результат
}
//расчет и вывод строки таблицы истинности
//параметры:
//ОПН, номер строки, количество переменных
void print_table(char* opn, int row, int cnt)
{
	int      i;
	for (i = 0; i<cnt; i++)
	{
		printf("%d ", (((1 << (cnt - i - 1)) & row) != 0));   //вывод значений переменных (о маске бита смотри выше)
	}
	printf("%d\n", F(opn, row, cnt));            //расчет и вывод значения функции
}
int main()
{
	char   str[256];               //входная строка
	char   opn[256];               //строка ОПН
	int      i;
	int      cnt;                  //количество переменных
	int      max;                  //число строк таблицы истинности
	printf("Enter function: ");
	std::cin >> str;                     //вводим строку
	if ((cnt = OPN(str, opn))>0)      //пребразовываем в ОПН (с проверкой на синтаксис).
	{                           //одновременно получаем количество переменных
		print_opn(opn);               //выведем строку ОПН
		print_header(cnt);            //заголовок таблицы истинности (по кол элементов)
		max = 1 << cnt;              //количество строк таблицы истинности
		for (i = 0; i<max; i++)
			print_table(opn, i, cnt);   //расчет и вывод очередной строки ТИ
	}
	else
		printf("Syntax error...\n");   //ошибка! Получили cnt=-1
	_getch();
	return 0;
}