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

题意：

给你一个带括号、加减、乘的表达式，和n个数$(n\leq 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-;

const int mod = 1e9+;

const int maxn = 5e6+;

const int maxm = 2e6+;

const int inf = 0x3f3f3f3f;

const db pi = acos(-1.0);

int a[];

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 = ;

    stack<int>stt;

    for(int i = ; 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 = ; i <= n; i++){

            scanf("%d", &a[i]);

        }

        sort(a+, a++n);

        int v;

        scanf("%d", &v);

        if(n==&&v==)break;

        getchar();

        scanf("%s", s);

        int m = strlen(s);

        set<char>ss;

        vector<char>wzs;

        top = ;

        for(int i = ; 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+, a+n+);

        int flg = ;

        do{

            if(fun()==v){

                flg = ;

                printf("YES\n");

                break;

            }

        }while(next_permutation(a+, a+n+));

        if(!flg)printf("NO\n");

    }

    return ;

}

巴特西

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

最新文章

热门文章