题目
先看样例：
6
16=1+2*3
7*8*9=54
1+1=1+22
4*6=22+2
15+7=1+2
11+1=1+5
n表示输入n行数据，下面每一行数据表示一个等式。如果能满足 在等式中添加任意一个数字 使得等式两边成立，则输出Yes，否则输出No。如果等式本来就相等，也输出Yes。
符号只有+，*和=。都是正整数。
想测试自己的拆分或计算是否正确，可以只使用一个样例：
1
16=1+2*3
思路
过程略微复杂的模拟题。
想要进行计算，需要将等式（字符串）拆分为数字和字符。计算过程类似于逆波兰表达式，用栈来实现。至于是否存在添加一个数字使得等式成立，我们可以枚举。
本题解C++。（这种数据输入感觉用C++会方便，如果用JS需要异步？？360的编程题竟然没有给输入的模板，直接ACM模式 ）
输入字符串，得到数字和字符的函数：其中cntNum、cntCh等是指针，用来记录一共拆分出了多少数。
void stringTo(string a){
int temp=0;
for(int i=0;a[i];i++){
if(a[i]>='0'&&a[i]<='9'){
temp*=10;
temp+=a[i]-'0';
}else{
ch[cntCh]=a[i];
cntCh++;
num[cntNum]=temp;
cntNum++;temp=0;
}
}
num[cntNum]=temp;
cntNum++;temp=0;
}
对等号=左右两边的数字进行计算，思想是逆波兰表达式。
这里的参数left、right表示计算数组中[left,right]的答案。这样，只需要改变参数就可以分别计算等号左边和等号右边。
注意，数字的数量会比符号多1，因此可以先把第一个数字压入栈。
//计算左右两边的大小
//左 1,indexx
//右 indexx+1,end
int cal(int left,int right){
if(left==right) return num[left];
stack<int>numm;stack<char>chh;
numm.push(num[left]);
// 数字
for(int i=left+1;i<=right;i++){
//对应的操作符是i-1的下标
char op=ch[i-1];
//优先级高
if(op=='*'){
int qian=numm.top();numm.pop();
int hou=num[i];
int temp=qian*hou;
numm.push(temp);
}
else{
numm.push(num[i]);
chh.push(ch[i-1]);
}
}
// 计算加减
while(chh.size()){
char op=chh.top();chh.pop();
int hou=numm.top();numm.pop();
int qian=numm.top();numm.pop();
int temp=qian+hou;
numm.push(temp);
}
return numm.top();
}
枚举在字符串中每一个位置都插入一个数字并计算：
for(int i=0;a[i];i++){
c.clear();
b+=a[i];
c+=b;
for(int j=0;j<=9;j++){
c+=char('0'+j);
c+=a.substr(i+1);
if(solve(c)) {
flag=1;break;
}
c.clear();c+=b;
}
if(flag) break;
}
总体的过程：将字符串转换为数字和符号、计算。这个过程可以封装一下：
bool solve(string a){
clearr();
stringTo(a);
findEqual();
l=cal(0,indexx);
r=cal(indexx+1,cntNum-1);
if(l==r) return true;
else return false;
}
总体代码（AC）
#include<bits/stdc++.h>
using namespace std;
int t;string a;
int num[5000];
char ch[5000];
int cntNum=0,cntCh=0;
int indexx;//=的下标
int l,r;
void clearr(){
cntNum=0,cntCh=0;
}
void stringTo(string a){
int temp=0;
for(int i=0;a[i];i++){
if(a[i]>='0'&&a[i]<='9'){
temp*=10;
temp+=a[i]-'0';
}else{
ch[cntCh]=a[i];
cntCh++;
num[cntNum]=temp;
cntNum++;temp=0;
}
}
num[cntNum]=temp;
cntNum++;temp=0;
}
//找到=的下标index 对应num的下标，index及其之前的都是=号左边的
void findEqual(){
for(int i=0;i<cntCh;i++){
if(ch[i]=='='){
indexx=i;break;
}
}
}
//计算左右两边的大小
//左 1,indexx
//右 indexx+1,end
int cal(int left,int right){
if(left==right) return num[left];
stack<int>numm;stack<char>chh;
numm.push(num[left]);
// 数字
for(int i=left+1;i<=right;i++){
//对应的操作符是i-1的下标
char op=ch[i-1];
//优先级高
if(op=='*'){
int qian=numm.top();numm.pop();
int hou=num[i];
int temp=qian*hou;
numm.push(temp);
}
else{
numm.push(num[i]);
chh.push(ch[i-1]);
}
}
// 计算加减
while(chh.size()){
char op=chh.top();chh.pop();
int hou=numm.top();numm.pop();
int qian=numm.top();numm.pop();
int temp=qian+hou;
numm.push(temp);
}
return numm.top();
}
bool solve(string a){
clearr();
stringTo(a);
findEqual();
l=cal(0,indexx);
r=cal(indexx+1,cntNum-1);
if(l==r) return true;
else return false;
}
int main(){
cin>>t;
while(t--){
clearr();l=0,r=0;
cin>>a;
stringTo(a);
// 找= index
findEqual();
l=cal(0,indexx);
r=cal(indexx+1,cntNum-1);
if(l==r) {
cout<<"Yes"<<endl;continue;
}
string b,c;int flag=0;
//在最前面加
for(int i=0;i<=9;i++){
c.clear();
c+=char('0'+i);
c+=a;
if(solve(c)) {
flag=1;break;
}
}
if(flag) {
cout<<"Yes"<<endl;continue;
}
b.clear();c.clear();
for(int i=0;a[i];i++){
c.clear();
b+=a[i];
c+=b;
for(int j=0;j<=9;j++){
c+=char('0'+j);
c+=a.substr(i+1);
if(solve(c)) {
flag=1;break;
}
c.clear();c+=b;
}
if(flag) break;
}
if(flag) {
cout<<"Yes"<<endl;continue;
}
else cout<<"No"<<endl;
}
return 0;
}
不重要心得
很典型且要素很多的模拟题，字符串的计算+逆波兰表达式+枚举。写了70多分钟！
输入的数据范围并不大，所以枚举可以实现。不知道有没有更好的写法。
代码写的乱乱的，也不精简，等有空的时候重新写一下。
另外：我是前端啊！但是看到编程题没有给异步输入数据的模板的时候傻眼了。。这咋做。。被迫捡起用C++打题的记忆了，不然就寄了。
