全⾃动数字论证机（迫真）
全⾃动数字论证机（迫真）
众所周知，OIer都事HOMO。本⼩⿁在看到知乎上问题后想起来以前暑假集训⽆聊的时候写的⼀个数字论证搜索，于是来写博客由于python我没怎么⽤过，所以还是⽤的c++写的，并且事在晚上订正完考试写的，所以稍微有些⿇烦。
谢谢茄⼦！
数据库⽣成
⼤体思路就事⽣成⼀个排列，然后通过现成的计算器⽣成答案并且保存。
⽣成排列
dfs即可。代码如下，主要⽤栈模拟
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<ctime>
#include<cstdlib>
#include<stack>
#include<cstring>
#include<cmath>
#include<windows.h>
#pragma -g -std=c++11
using namespace std;
int t=0;
const int num[7]={0,1,1,4,5,1,4};
char s[10]={0,'+','-','*','/','^','!'};
const int mulj[4][7]={{0,0,0,0,0,0,0},{0,1,1,2,1,1,2},{0,0,0,4,2,0,4},{0,0,0,0,0,0,0}};
const int lenj[7]={0,1,1,2,3,1,2};
string ss;
int maxn=0;
int numb=0;
stack<char>ans;
const int MAX = 30;
const int DONE = 1;
//栈定义
template <class T>
class Stack{
public:
Stack(int MaxStackSize=10);
printf怎么加endl~Stack() { delete [] stack;}
bool IsEmpty() const {return top==-1;}
bool IsFull() const {return top==MaxTop;}
T Top() const;
Stack<T>& Add(const T& x);
Stack<T>& Del(T& x);
void MakeEmpty(){top=-1;} //清空栈
void print(){
for(int i; i < top + 1; i ++){
cout<<stack[i]<<'\t';
}
cout<<endl;
private:
int top;//栈顶
int MaxTop;//最⼤的栈顶值
T *stack;//堆栈元素数组
template<class T>
Stack<T>::Stack(int MaxStackSize){
MaxTop=MaxStackSize-1;
stack=new T[MaxStackSize];
top=-1;
template<class T>
Stack<T>& Stack<T>::Add(const T& x){
if(IsFull())
{cout<<"no memory;"<<endl;return *this;}
top=top+1;
stack[top]=x;
return *this;
template<class T>
Stack<T>& Stack<T>::Del(T& x){
if(IsEmpty())
{cout<<"no element"<<endl;return *this;}
template<class T>
T Stack<T>::Top() const{
return stack[top];
//判断⼀个字符是否为数字
bool isNum(char c){
if((c > '0'||c == '0')&&(c < '9'||c == '9'))
return true;
else
return false;
/
/删除字符串中的空格
void deleteBlank(string &s){
string::iterator i = s.begin();
while ((i=find(i, s.end(), ' '))!=s.end())
//计算器
class Calculator{
public:
Calculator(string s);
~Calculator();
int outPriority(char); //返回栈外优先级
int inPriority(char); //返回栈内优先级
bool judgePri(char, char); //判断优先级前⼀个为栈外符号，后⼀个为栈内符号若前⼤于后返回1，否则返回0 int judgePri(char); //判断运算符若是'#'返回 -1，若是')'返回 0，否则返回 1
void dealNum(); //处理数据
int calculate(); //计算
void setString(string const s){
this->s = '#' + s + '#';
deleteBlank(this->s); //删除字符串中的空格
private:
Stack<char> *s_sym; //符号栈
Stack<int> *s_num; //数据栈
string s;
Calculator::Calculator(string s){
this->s = '#' + s + '#';
deleteBlank(this->s);
s_sym = new Stack<char>(MAX);
s_num = new Stack<int>(MAX);
Calculator::~Calculator(){
delete s_sym;
delete s_num;
int Calculator::outPriority(char symble){
switch(symble){
case '#':
return 0;
case '(':
return 8;
case '+':
return 2;
case '-':
return 2;
case '*':
return 4;
case '/':
return 4;
case '%':
return 4;
case '^':
return 6;
case ')':
return 1;
default:
throw 1;
int Calculator::inPriority(char symble){
case '(':
return 1;
case '+':
return 3;
case '-':
return 3;
case '*':
return 5;
case '/':
return 5;
case '%':
return 5;
case '^':
return 7;
case ')':
return 8;
default:
throw 1;
bool Calculator::judgePri(char out, char in){
if(outPriority(out) > inPriority(in))
return true;
else
return false;
int Calculator::judgePri(char symble){
if(symble == '#')
return -1;
else if(symble == ')')
return 0;
else
return 1;
void Calculator::dealNum(){
//将数据栈中的前两个弹出进⾏计算，结果放回数据栈，符号栈弹出顶部元素
char _temp = 0;
int dtemp1 = 0;
int dtemp2 = 0;
s_sym->Del(_temp);
s_num->Del(dtemp1);
s_num->Del(dtemp2);
switch(_temp){
case '+':
dtemp2 += dtemp1;
break;
case '-':
dtemp2 = dtemp2 - dtemp1;
break;
case '*':
dtemp2 = dtemp2 * dtemp1;
break;
case '/':
if(dtemp1 == 0)
throw 0;
else
dtemp2 = dtemp2 / dtemp1;
break;
case '%':
dtemp2 = dtemp2 % dtemp1;
break;
case '^':
dtemp2 = pow(dtemp2,dtemp1);
break;
default:
throw 1;
s_num->Add(dtemp2);
int Calculator::calculate(){
for(int i = 0; i < s.size(); i ++){ //遍历字符串
if(isNum(s[i])){
int temp = (int)(s[i]) - 48; //char强制类型转换为int ascii 码数值，减 48 转换为对应整数值 int _temp = 0;
if(i > 0 && isNum(s[i - 1])){
s_num->Del(_temp);
s_num->Add(temp);
}else{
char temp = s[i];
if(s_sym->IsEmpty()){
s_sym->Add(temp);
}else{
if(judgePri(temp, s_sym->Top())){
s_sym->Add(temp);
}else if(judgePri(temp) == 1){ //栈外优先级⼩于栈内优先级，且不为 '#' 和 ')'
while(!judgePri(temp, s_sym->Top())){ //当栈外优先级⽐栈内优先级低时，执⾏栈内符号运算 dealNum();
}
s_sym->Add(temp);
}else if (judgePri(temp) == -1){
while(s_sym->Top() != '#'){
dealNum();
}
int result = s_num->Top();
s_sym->MakeEmpty();
s_num->MakeEmpty();
return result;
}
else if(judgePri(temp) == 0){
while(s_sym->Top() != '('){
dealNum();
}
s_sym->Del(temp);
}
}
}
char nnans[101];
void exc(){
stack<char>st;
while(!pty()){
st.p());ans.pop();
int rs=-1,sta=1,nnn=0;
ss="";
while(!st.empty()){
char p();ans.push(now);st.pop();
ss+=now;
//Calculator c("");
int po=0;int numc=0;
for(int i=0;i<ss.length();i++){
if('0'<=ss[i]&&ss[i]<='9'&&!('0'<=ss[i+1]&&ss[i+1]<='9')) nnn++;
if(nnn==6) {
po = i;
break;
}
int dd=ss.length();
for(int i=po+1;i<dd;i++) ss.pop_back();
for(int i=0;i<ss.length();i++){
if(ss[i]=='(') numc++;
if(ss[i]==')') numc--;
while(numc--) ss+=')';
cout<<ss<<endl;
/
*c.setString(ss);
printf("%d = ",c.calculate());
nnn=0;
for(int i=0;i<ss.length();i++){
if(nnn==6&&ss[i]!=')') break;
if(ss[i]=='2'&&ss[i+1]=='4'){
printf("4!");i++;nnn++;
}else if(ss[i]=='1'&&ss[i+1]=='2'){
printf("5!");i+=2;nnn++;
}else if(ss[i]=='('&&ss[i+1]==')'){
i++;
}else{
printf("%c",ss[i]);if('1'<=ss[i]&&ss[i]<='9') nnn++;
}
void out(){
stack<char>st;
while(!pty()){
//printf("%d\n",ans.size());
char p();
st.push(sk);ans.pop();
while(!st.empty()){
char p();ans.push(now);st.pop();
printf("%c",now);
putchar(10);
Sleep(500);
void dfs(int lev){
if(lev==6){
int tmp=numb;
while(numb--){
ans.push(')');
}
exc();
numb=tmp;
while(tmp--){
ans.pop();
}
return;
lev++;
for(int i=1;i<=5;i++){
for(int k=1;k<=lenj[lev];k++) ans.push(mulj[k][lev]+'0'); if(lev!=1) ans.push(')'),numb--;
ans.push(s[i]);
ans.push('('),numb++;
//out();
dfs(lev);
for(int k=1;k<=lenj[lev];k++) ans.pop();
if(lev!=1) ans.pop(),numb++;
ans.pop();
ans.pop();
numb--;
ans.push(char(num[lev]+'0'));
if(lev!=1) ans.push(')'),numb--;
ans.push(s[i]);
ans.push('('),numb++;
//out();
dfs(lev);
if(lev!=1) ans.pop(),numb++;
numb--;
ans.pop();
ans.pop();
ans.pop();
for(int k=1;k<=lenj[lev];k++) ans.push(mulj[k][lev]+'0'); ans.push(s[i]);
ans.push('('),numb++;
//out();
dfs(lev);
for(int k=1;k<=lenj[lev];k++) ans.pop();
ans.pop();
numb--;
ans.pop();
ans.push(num[lev]+'0');
ans.push(s[i]);
ans.push('('),numb++;
//out();
dfs(lev);
ans.pop();
ans.pop();
ans.pop();
numb--;
return;
发表评论