表达式求值
2023-08-19 10:12:08
发布于：日本
1阅读
0回复
0点赞
#include<bits/stdc++.h>
using namespace std;
string ops = "*+-/"; // *42 +43 -45 /47
map<int, string> num_str; // 9 : "4+4+4/4"
//map<string, int> str_num; // "4+4+4/4" : 9
int get_value(string exp){ //4+4+4/4 -> 9
stack<char> o;
stack<int> nums;
nums.push(4);
for(int i=1; i<exp.size(); i+=2){
if(exp[i] == '+'){
o.push('+');
nums.push(4);
}else if(exp[i] == '-'){
o.push('+');
nums.push(-4);
}else if(exp[i] == '*'){
int a = nums.top();
nums.pop();
nums.push(a * 4);
}else{
int a = nums.top();
nums.pop();
nums.push(a / 4);
}
}
while(o.size()){
int b = nums.top();
nums.pop();
int a = nums.top();
nums.pop();
char op = o.top();
o.pop();
if(op == '+') nums.push(a + b);
else if(op == '-') nums.push(a - b);
}
return nums.top();
}
void test(){
assert(get_value("4-4/4-4") == -1);
assert(get_value("4*4-4/4") == 15);
assert(get_value("4+4+4/4") == 9);
assert(get_value("4*4+4/4") == 17);
assert(get_value("4+4-4/4") == 7);
}
void init(){
for(int i=0; i<4; i++){
for(int j=0; j<4; j++){
for(int k=0; k<4; k++){
string t = "4?4?4?4";
t[1] = ops[i]; //*
t[3] = ops[j]; //*
t[5] = ops[k]; //+
int num = get_value(t);
if(num_str[num].size() == 0){
num_str[num] = t;
}
}
}
}
}
void show(string exp){ // 4+4+4/4 -> 4 + 4 + 4 / 4
for(auto x : exp){
cout << x << " ";
}
}
int main(){
// test();
freopen("fourth.in", "r", stdin);
freopen("fourth.out", "w", stdout);
int m; cin>>m;
init();
// for(int i=-256; i<=256; i++){
// cout << i << " : " << num_str[i] << endl;
// }
while(m--){
int n; cin>>n;
if(num_str[n].size()){
show(num_str[n]);
cout << "= ";
cout << n << endl;
}else{
puts("no solution");
}
}
fclose(stdin);
fclose(stdout);
return 0;
}
这里空空如也
有帮助，赞一个