#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;
}
Если Вы уже зарегистрированы на Портале - войдите в систему, если Вы еще не регистрировались - пройдите простую процедуру регистрации.