前言
由于过于拙劣,离散数学老师要求我们用代码实现离散数学的一些题目,说白了就是oi题,程序设计也要求一些oi的东西。hgame2022出题人chuj也出了一道和spfa有关的题目,所以俺的oi之魂又被重新点燃。想着记录一下上大学(省二退役两年)之后新的oi进展。
但本人主要还是pwn,想跟着我搞oi那就大错特错了。
1.【2022/3/1】简单的逻辑表达式计算
前置知识
二元运算符的表达式计算:建议百度一下前中后缀表达式
思路
之前做过一个四则运算的表达式计算,但是四则运算是二元的,题目有一个非运算不太好处理。当时改了很多次,和oi👴logging改了半天,全在改非运算。个人也是很满意自己对非运算的处理,大体上是没啥问题,就是卡在一些很烦人的细节上了。
首先是关于这些ABCD的未知数的处理,由于只有四个,所以博主偷懒使用了循环。但是如果遇上n个变量就不行了,只能用递归然后把生成的序列放入数组。开一个bool数组标记未知数的位置,那么在循环遍历整个算式的时候,我们就可以和经典做法一样用栈分开储存数和运算符了。
关键点
这题的关键就是对非运算的处理了。我的思路如下:
读到‘!’是只有两种情况,下一位是数字或者是括号
(1)如果!的下一位是数字,那么把数字先push然后再push一个-1
(2)如果!的下一位是‘(’,那么就把!入符号栈
相关代码:
if(s[m]=='!') //对'!' 要特殊处理
{
if(s[m+1]=='(') op.push(s[m]);
else
{
if(s[m+1]=='A') num.push(i);
else if(s[m+1]=='B') num.push(j);
else if(s[m+1]=='C') num.push(k);
else num.push(ll);
num.push(-1);
m++;
}
}
取数出来做运算:(试试!(!A))你就知道一个数之前可能不止一个-1了
int num_out()
{
int ss=0,t;
while(!num.empty() && num.top()==-1)
{
num.pop();
ss++;
}
t=num.top();
if(!num.empty()) num.pop();
if(ss & 1) return !t;
else return t;
}
完整代码
#include<stack>
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
bool f[30000];
char s[30000];
stack<int> num;
stack<char> op;
int num_out()
{
int ss=0,t;
while(!num.empty() && num.top()==-1)
{
num.pop();
ss++;
}
t=num.top();
if(!num.empty()) num.pop();
if(ss & 1) return !t;
else return t;
}
int caculate(int a,int b, char c)
{
if(c=='^') return (a && b);
else if(c=='+') return (a || b);
else if(c=='>') return ( !a || b);
else return ((!a && !b) || (a && b));
}
void stack_init()
{
while(!num.empty()) num.pop();
while(!op.empty()) op.pop();
}
int yxj(char c)
{
if(c=='^' || c=='+') return 4;
else if(c=='>') return 3;
else if(c=='-') return 2;
return 1;
}
int main()
{
int n;
cin>>n;
if(scanf("%s",s+1)){};
int l=strlen(s+1);
for(int i=1;i<=l;i++)
if(s[i]>='A' && s[i]<='A'+n-1)
f[i]=1;
if(n==1)
{
for(int i=0;i<=1;i++)
{
stack_init();//把栈都清空
for(int m=1;m<=l;m++)
{
if(f[m]) num.push(i);
else //如果是操作符
{
if(s[m]=='!') //对'!' 要特殊处理
{
if(s[m+1]=='(') op.push(s[m]);
else
{
num.push(i);
num.push(-1);
m++;
}
}
else if(s[m]=='(') op.push(s[m]); //左括号直接入
else if(s[m]==')') //右括号的话直接计算左括号到右括号的所有值
{
while(!op.empty() && op.top()!='(')
{
char c=op.top();
op.pop();
int b=num_out();
int a=num_out();
int res=caculate(a,b,c);
num.push(res);
}
if(!op.empty()) op.pop();
if(!op.empty() && op.top()=='!')
{
num.push(-1);
op.pop();
}
}
else //如果是其它二元运算符
{
if(op.empty()) op.push(s[m]) ; //如果符号栈为空那么直接入
else
{
while(!op.empty() && yxj(s[m])<=yxj(op.top()))
{
char c=op.top();
op.pop();
int b=num_out();
int a=num_out();
int res=caculate(a,b,c);
num.push(res);
}
op.push(s[m]);
}
}
}
}
while(!op.empty()) //如果符号栈不为空
{
char c=op.top();
op.pop();
int b=num_out();
int a=num_out();
int res=caculate(a,b,c);
num.push(res);
}
printf("%d %d\n",i,num_out());
}
}
else if(n==2)
{
for(int i=0;i<=1;i++)
for(int j=0;j<=1;j++)
{
stack_init();//把栈都清空
for(int m=1;m<=l;m++)
{
if(f[m]) //如果是数字
{
if(s[m]=='A') num.push(i);
else num.push(j);
}
else //如果是操作符
{
if(s[m]=='!') //对'!' 要特殊处理
{
if(s[m+1]=='(') op.push(s[m]);
else
{
if(s[m+1]=='A') num.push(i);
else if(s[m+1]=='B') num.push(j);
num.push(-1);
m++;
}
}
else if(s[m]=='(') op.push(s[m]); //左括号直接入
else if(s[m]==')') //右括号的话直接计算左括号到右括号的所有值
{
while(!op.empty() && op.top()!='(')
{
char c=op.top();
op.pop();
int b=num_out();
int a=num_out();
int res=caculate(a,b,c);
num.push(res);
}
op.pop();
if(!op.empty() && op.top()=='!')
{
num.push(-1);
op.pop();
}
}
else //如果是其它二元运算符
{
if(op.empty()) op.push(s[m]) ; //如果符号栈为空那么直接入
else
{
while(!op.empty() && yxj(s[m])<=yxj(op.top()))
{
char c=op.top();
op.pop();
int b=num_out();
int a=num_out();
int res=caculate(a,b,c);
num.push(res);
}
op.push(s[m]);
}
}
}
}
while(!op.empty()) //如果符号栈不为空
{
char c=op.top();
op.pop();
int b=num_out();
int a=num_out();
int res=caculate(a,b,c);
num.push(res);
}
if(num.top()==-1)
{
num.pop();
int t=num.top();
num.pop();
num.push(!t);
}
printf("%d %d %d\n",i,j,num_out());
}
}
else if(n==3)
{
for(int i=0;i<=1;i++)
for(int j=0;j<=1;j++)
for (int k=0;k<=1;k++)
{
stack_init();//把栈都清空
for(int m=1;m<=l;m++)
{
if(f[m]) //如果是数字
{
if(s[m]=='A') num.push(i);
else if(s[m]=='B') num.push(j);
else num.push(k);
}
else //如果是操作符
{
if(s[m]=='!') //对'!' 要特殊处理
{
if(s[m+1]=='(') op.push(s[m]);
else
{
if(s[m+1]=='A') num.push(i);
else if(s[m+1]=='B') num.push(j);
else if(s[m+1]=='C') num.push(k);
num.push(-1);
m++;
}
}
else if(s[m]=='(') op.push(s[m]); //左括号直接入
else if(s[m]==')') //右括号的话直接计算左括号到右括号的所有值
{
while(!op.empty() && op.top()!='(')
{
char c=op.top();
op.pop();
int b=num_out();
int a=num_out();
int res=caculate(a,b,c);
num.push(res);
}
op.pop();
if(!op.empty() && op.top()=='!')
{
num.push(-1);
op.pop();
}
}
else //如果是其它二元运算符
{
if(op.empty()) op.push(s[m]) ; //如果符号栈为空那么直接入
else
{
while(!op.empty() && yxj(s[m])<=yxj(op.top()))
{
char c=op.top();
op.pop();
int b=num_out();
int a=num_out();
int res=caculate(a,b,c);
num.push(res);
}
op.push(s[m]);
}
}
}
}
while(!op.empty())
{
char c=op.top();
op.pop();
int b=num_out();
int a=num_out();
int res=caculate(a,b,c);
num.push(res);
}
printf("%d %d %d %d\n",i,j,k,num_out());
}
}
else
{
for(int i=0;i<=1;i++)
for(int j=0;j<=1;j++)
for (int k=0;k<=1;k++)
for(int ll=0;ll<=1;ll++)
{
stack_init();//把栈都清空
for(int m=1;m<=l;m++)
{
if(f[m]) //如果是数字
{
if(s[m]=='A') num.push(i);
else if(s[m]=='B') num.push(j);
else if(s[m]=='C') num.push(k);
else num.push(ll);
}
else //如果是操作符
{
if(s[m]=='!') //对'!' 要特殊处理
{
if(s[m+1]=='(') op.push(s[m]);
else
{
if(s[m+1]=='A') num.push(i);
else if(s[m+1]=='B') num.push(j);
else if(s[m+1]=='C') num.push(k);
else num.push(ll);
num.push(-1);
m++;
}
}
else if(s[m]=='(') op.push(s[m]); //左括号直接入
else if(s[m]==')') //右括号的话直接计算左括号到右括号的所有值
{
while(!op.empty() && op.top()!='(')
{
char c=op.top();
op.pop();
int b=num_out();
int a=num_out();
int res=caculate(a,b,c);
num.push(res);
}
op.pop();
if(!op.empty() && op.top()=='!')
{
num.push(-1);
op.pop();
}
}
else //如果是其它二元运算符
{
if(op.empty()) op.push(s[m]) ; //如果符号栈为空那么直接入
else
{
while(!op.empty() && yxj(s[m])<=yxj(op.top()))
{
char c=op.top();
op.pop();
int b=num_out();
int a=num_out();
int res=caculate(a,b,c);
num.push(res);
}
op.push(s[m]);
}
}
}
}
while(!op.empty())
{
char c=op.top();
op.pop();
int b=num_out();
int a=num_out();
int res=caculate(a,b,c);
num.push(res);
}
printf("%d %d %d %d %d\n",i,j,k,ll,num_out());
}
}
return 0;
}