Грымзик » 25 авг 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;
}
Если не обязательно именно строить дерево как структуру, то вот прога.
В ней строка справа-налево просматривается, пока правая часть не образует
правильное скобочное выражение. Далее функция рекурсивно вызывается
от получившихся правой и левой частей. Может неправильно написано
вычислении импликации (0 только если 0->1 ?)
[code]#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;
}[/code]