PDA

Просмотр полной версии : Вычисление логических выражений при помощи бинарного дерева



koly4ii
24.08.2009, 11:50
Ребят помогите кто-нибудь, горю!
Необходимо написать программу вычисляющую логические выражения с помощью бинарных деревьев.
Т.е. например пусть | - дизьюнкция, & - коньюнкция, -> - импликация; надо чтобы после ввода такой формулы, например, (0 & 1 | 1) -> 0 выдавал ответ (в данном случае единицу).
Мне хотябы былоб от чего оттолкнуться, если кто-нибудь может хотябы для одной функции написать - напишите пожалуйста...

Грымзик
25.08.2009, 22:00
Если не обязательно именно строить дерево как структуру, то вот прога.
В ней строка справа-налево просматривается, пока правая часть не образует
правильное скобочное выражение. Далее функция рекурсивно вызывается
от получившихся правой и левой частей. Может неправильно написано
вычислении импликации (0 только если 0->1 ?)

#include <iostream>
#include <string>
using namespace std;

string delete_spaces(string str)
{
string s="";
for (int i=0; i<str.size(); ++i)
{
if (str[i]!=' ' && str[i]!='\t')
s+=str[i];
}
return s;
}

bool check(string str)
{
string s=delete_spaces(str);

if (s.size()==1 && s=="0")
return 0;
if (s.size()==1 && s=="1")
return 1;
int q=0;

string s1, s2;


for (int i=s.size()-1; i>=0; --i)
{

if (i==0 && s[i]=='(' && q==1)
{
s.assign(s, 1, s.size()-2);
i=s.size()-1;
q=0;
}


if (s[i]==')')
q+=1;
if (s[i]=='(')
q-=1;

if (q==0 && s[i]=='|')
{
s1.assign(s, 0, i);
s2.assign(s, i+1, s.size()-i-1);
return check(s1)||check(s2);
}
if (q==0 && s[i]=='&')
{
s1.assign(s, 0, i);
s2.assign(s, i+1, s.size()-i-1);
return check(s1)&&check(s2);
}
if (q==0 && s[i]=='>')
{
s1.assign(s, 0, i-1);
s2.assign(s, i+1, s.size()-i-1);
if (!check(s1) && check(s2))
return 0;
else return 1;
}
}
}


int main()
{

string s;
getline(cin,s);
cout<<check(s);
return 0;
}

koly4ii
26.08.2009, 10:26
Если не обязательно именно строить дерево как структуру...

Я если честно сам не совсем уверен, ибо столкнулся с множеством проблем пытаясь решить эту задачу выстраивая дерево структурой, которые так и не решил. Спасибо за предложенный вариант, я что-то даже не подумал о такой возможности. Теперь будет решена хоть каким-то способом =))

Может неправильно написано
вычислении импликации (0 только если 0->1 ?)

Это уже не столь важно, важен сам алгоритм. А так 0 только когда 1->0 =)
Ещё раз спасибо за предложенный вариант!