HDU4192 Guess the Numbers(表达式计算、栈)

题意：

给你一个带括号、加减、乘的表达式，和n个数$(nleq 5)$，问你带入这几个数可不可能等于n

思路：

先处理表达式：先将中缀式转化为逆波兰表达式

转换过程需要用到栈，具体过程如下：
1）如果遇到操作数，我们就直接将其输出。
2）如果遇到左括号时我们也将其放入栈中。
3）如果遇到一个右括号，则将栈元素弹出，将弹出的操作符输出直到遇到左括号为止。注意，左括号只弹出并不输出。
4）如果遇到任何其他的操作符，如（“+”， “*”，“（”）等，从栈中弹出元素直到遇到发现更低优先级的元素(或者栈为空)为止。弹出完这些元素后，才将遇到的操作符压入到栈中。有一点需要注意，只有在遇到" )"的情况下我们才弹出" ( "，其他情况我们都不会弹出" ( "。
5）如果我们读到了输入的末尾，则将栈中所有元素依次弹出。

然后用n个数的全排列代入，注意全排列函数next_permutation的使用方式，用do-while避免了漏第一个排列的情况，用之前要先sort

代码：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<string>
#include<stack>
#include<queue>
#include<deque>
#include<set>
#include<vector>
#include<map>
#include<functional>
    
#define fst first
#define sc second
#define pb push_back
#define mem(a,b) memset(a,b,sizeof(a))
#define lson l,mid,root<<1
#define rson mid+1,r,root<<1|1
#define lc root<<1
#define rc root<<1|1
#define lowbit(x) ((x)&(-x)) 

using namespace std;

typedef double db;
typedef long double ldb;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> PI;
typedef pair<ll,ll> PLL;

const db eps = 1e-6;
const int mod = 1e9+7;
const int maxn = 5e6+2;
const int maxm = 2e6+100;
const int inf = 0x3f3f3f3f;
const db pi = acos(-1.0);
int a[10];
int top;
char s[maxn];
stack<char>num, op;
bool isnum(char c){
    if(c>='a' && c <='z') return true;
    return false;
}
bool rk(char a, char b){
    if(a == '*' && (b == '+' || b == '-') ) return true;
    return false;
}

char tmp[maxn];

int fun(){
    int ind = 1;
    stack<int>stt;
    for(int i = 0; i < top; i++){
        if(isnum(tmp[i])){
            stt.push(a[ind++]);
        }
        else{
            int t1 = stt.top();
            stt.pop();
            int t2 = stt.top();
            stt.pop();
            if(tmp[i]=='+')stt.push(t1+t2);
            if(tmp[i]=='-')stt.push(t1-t2);
            if(tmp[i]=='*')stt.push(t1*t2);
        }
    }
    return stt.top();
}

int main(){
    int n;
    while(~scanf("%d", &n)){
        for(int i = 1; i <= n; i++){
            scanf("%d", &a[i]);
        }
        sort(a+1, a+1+n);
        int v;
        scanf("%d", &v);
        if(n==0&&v==0)break;
        getchar();
        scanf("%s", s);
        int m = strlen(s);
        set<char>ss;
        vector<char>wzs;
        top = 0;
        for(int i = 0; i < m; i++){
            if(isnum(s[i])){
                if(ss.find(s[i])==ss.end()){
                    ss.insert(s[i]);
                    wzs.pb(s[i]);
                }
                
                tmp[top++] = s[i];
                continue;
            }
            if(s[i]=='('){
                op.push(s[i]);
                continue;
            }
            if(s[i]==')'){
                while(op.top()!='('){
                    tmp[top++] = op.top();
                    op.pop();
                }
                op.pop();
                continue;
            }
            if(s[i]=='*'||s[i]=='+'||s[i]=='-'){
                while(!(op.empty()||op.top()=='('||rk(s[i], op.top()))){
                    tmp[top++] = op.top();
                    op.pop();
                }
                if((op.empty()||op.top()=='('||rk(s[i], op.top()))){
                    op.push(s[i]);
                }
            }

        }
        sort(a+1, a+n+1);
        int flg = 0;
        do{
            if(fun()==v){
                flg = 1;
                printf("YES
");
                break;
            }
        }while(next_permutation(a+1, a+n+1));
        if(!flg)printf("NO
");
    }
    return 0;
}