首页 > 搜索 > DFS搜索 > HDU 4192-Guess the Numbers-DFS-[解题报告]HOJ
2015
05-23

HDU 4192-Guess the Numbers-DFS-[解题报告]HOJ

Guess the Numbers

问题描述 :

John has never been very good at maths. Due to his bad grades, his parents have sent him to the Academic Coalition of Mathematics (ACM). Despite the large amount of money his parents are spending on the ACM,
John does not pay much attention during classes. However, today he has begun to think about all the e ffort his parents are putting into his education, and he has started to feel somewhat. . . guilty. So he has made a decision: he is going to improve his maths grades!
Game, Set and Match

However, no sooner had he resolved to pay attention than the lesson ended. So the only thing he has been able to do is to hurriedly copy the content of the blackboard in his notebook. Today, the teacher was explaining basic arithmetic expressions with unknowns. He vaguely remembers that his classmates have been substituting values into the unknowns to obtain the expressions’ results. However, in all the hurry, John has only written down expressions, values and results in a messy fashion. So he does not know which value comes with each unknown, or which result goes with each expression.
That is the reason he needs your help: he wants to know, given an expression, some values and a result, whether it is possible or not to assign those values to the unknowns in order for the expression to evaluate to the given result. The particular assignment of values does not matter to John, as he wants to do it by himself. He only wants to know whether it is possible or not.

输入:

Each test case in the input le consists of two lines:
 The fi rst line contains a sequence of natural numbers. The first one (1<=n<=5) is the number of unknowns that will occur in the expression. It is followed by a sequence of n integers v1 … vn (0<=vi<=50), which are the values to be assigned to the unknowns. Finally, there is an integer m (0<=m<=1000) representing the desired result of the evaluation of the expression.
 The second line contains an arithmetic expression composed of lowercase letters (a-z), brackets (( and )) and binary operators (+, -, *). This expression will contain n unknowns, represented by n di fferent lowercase letters, without repetitions. The expression will not contain any blanks and will always be syntactically correct, i.e. it is just an unknown or has the form (e1 op e2 ), where e1 and e2 are expressions and op is one of the three possible binary operators.
The input will finish with a dummy test case of just one line containing 0 0, which must not be processed.

输出:

Each test case in the input le consists of two lines:
 The fi rst line contains a sequence of natural numbers. The first one (1<=n<=5) is the number of unknowns that will occur in the expression. It is followed by a sequence of n integers v1 … vn (0<=vi<=50), which are the values to be assigned to the unknowns. Finally, there is an integer m (0<=m<=1000) representing the desired result of the evaluation of the expression.
 The second line contains an arithmetic expression composed of lowercase letters (a-z), brackets (( and )) and binary operators (+, -, *). This expression will contain n unknowns, represented by n di fferent lowercase letters, without repetitions. The expression will not contain any blanks and will always be syntactically correct, i.e. it is just an unknown or has the form (e1 op e2 ), where e1 and e2 are expressions and op is one of the three possible binary operators.
The input will finish with a dummy test case of just one line containing 0 0, which must not be processed.

样例输入:

3 2 3 4 14
((a+b)*c)
2 4 3 11
(a-b)
1 2 2
a
0 0

样例输出:

YES
NO
YES

题目在这里》

题意:给你一个中序表达式,由(、)、+、-、*以及a-z的小写字母组成,其中有n个不同的小写字母表示n个未知数,再给n个数分别表示这n个未知数的值,再给一个数m,求判断是否能够将这n个数分别赋值给这n个未知数代入表达式所算出的值恰为m。

思路:由于题目给的是中序表达式,不方便计算,所以要先将中序表达式转化为逆波兰式。

先来复习一下将一个中序表达式转化为逆波兰式的算法:

1:准备2个栈,一个存符号(记为栈1),另一个存变量(记为栈2);

2:依次读取中序表达式,

     (1)如果当前字符是‘(’,直接进栈1;

     (2)如果当前字符是‘)’,将符号栈栈顶元素依次弹入栈2,直至符号栈栈顶为‘(’,此时‘(’出栈;

     (3)如果是变量,直接进栈2;

     (4)如果是运算符

                 1》如果符号栈栈顶运算符优先级小于当前运算符优先级,或者符号栈为空或者符号栈栈顶元素为‘(’,直接进栈;

                2》如果符号栈栈顶运算符优先级大于等于当前运算符优先级,将符号栈栈顶元素依次弹入栈2,直到符号栈栈顶运算符优先级小于当前运算符优先级,当前运算符进栈1;

好了,将中序表达式转化为逆波兰式后就好办了,直接求n个数的全排列,然后用逆波兰式轻松求出表达式的值就简单多了,详情请见代码:

#include <iostream>
#include<cstdio>
#include<cstring>

using namespace std;

char stack1[20],stack2[20],str[20];
int top1,top2;
int n,m;
int v[10];
int flag;
int fv[10];
int cur[10];

int cal()
{
    int i,j;
    int lcm[10],len = 0;
    j = 0;
    for(i = 0;i < top2;i ++)
    {
        if(islower(stack2[i]))
            lcm[len ++] = cur[j ++];
        else
        {
            len --;
            switch(stack2[i])
            {
                case '+':lcm[len - 1] += lcm[len];
                break;
                case '-':lcm[len - 1] -= lcm[len];
                break;
                case '*':lcm[len - 1] *= lcm[len];
            }
        }
    }
    return lcm[0];
}

void dfs(int i,int cnt)
{
    if(flag)
        return;
    if(cnt == n - 1)
    {
        if(cal() == m)
        {
            flag = 1;
        }
        return;
    }
    int j;
    for(j = 0;j < n;j ++)
    {
        if(!fv[j])
        {
            fv[j] = 1;
            cur[cnt + 1] = v[j];
            dfs(j,cnt + 1);
            fv[j] = 0;
        }
    }
}

int main()
{
    int i;
    char c;
    while(scanf("%d",&n),n)
    {
        for(i = 0;i < n;i ++)
            scanf("%d",&v[i]);
        scanf("%d",&m);
        top1 = top2 = 0;
        scanf("%s",str);
        for(i = 0;i < strlen(str);i ++)
        {
            switch(str[i])
            {
                case '(':stack1[top1 ++] = str[i];
                break;
                case ')':while(stack1[top1 - 1] != '(')
                               stack2[top2 ++] = stack1[--top1];
                        top1 --;
                        break;
                case '*':if(top1 == 0 || stack1[top1 - 1] == '+'
                    || stack1[top1 - 1] == '-' || stack1[top1 - 1] == '(')
                            stack1[top1 ++] = '*';
                        else
                        {
                            while(stack1[top1 - 1] == '*')
                                stack2[top2 ++] = stack1[--top1];
                        }
                        break;
                case '+':
                case '-':if(stack1[top1 - 1] == '(' || top1 == 0)
                            stack1[top1 ++] = str[i];
                        else
                        {
                            while(stack1[top1 - 1] == '*')//stack1[top1 - 1] == '+' || stack1[top1 - 1] == '-')//之前写的有问题,竟然能过。。。
                                stack2[top2 ++] = stack1[--top1];
                        }
                        break;
                default:stack2[top2 ++] = str[i];
            }
        }
        flag = 0;
        for(i = 0;i < n;i ++)
        {
            memset(fv,0,sizeof(fv));
            fv[i] = 1;
            cur[0] = v[i];
            dfs(i,0);
        }
        if(flag)
            printf("YES\n");
        else
            printf("NO\n");
        /*for(i = 0;i < top2;i ++)
            printf("%c",stack2[i]);
        printf("\n");*/
    }
    return 0;
}
//62MS	324K

      

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/ophunter_lcm/article/details/8873040


, ,