当前位置：首页 > news >正文

UVa 11724 Evaluate the Expression

news 2026/7/15 19:59:12

题目描述

根据给定的BNF\texttt{BNF}BNF文法，一个数学表达式由变量（小写字母a到z）、运算符+和*以及括号()组成，运算遵循常规的优先级规则：括号优先，乘法优先于加法。要求给每个变量赋一个正整数，使得在满足所有给定的不等式约束（例如a > b表示aaa必须严格大于bbb）的前提下，表达式的值最小。若不等式矛盾，输出-1。

题目分析

本题包含三个主要难点：

表达式解析：需要按照优先级正确解析含有括号、加法和乘法的表达式，并能够替换变量值后求值。
变量约束建模：每个不等式x > y表示xxx的取值必须严格大于yyy的取值。由于所有变量都取正整数，这个关系可以转化为x≥y+1x \ge y + 1x≥y+1。
最小化赋值：为了使表达式结果最小，应让每个变量的取值尽可能小，同时满足所有不等式。这等价于在有向图中求出每个节点的最小可能值。

解题思路

1. 将不等式转化为有向图

考虑不等式x > y，因为变量都是正整数，所以等价于x≥y+1x \ge y + 1x≥y+1。
我们可以建一个有向图，从yyy向xxx连一条边，表示xxx的取值至少比yyy大111。

那么，每个变量的最小可能取值，就是图中从没有任何入边的节点（即没有“必须大于”其他变量的变量）出发，按照拓扑顺序递推得到的值：

初始时，所有入度为000的节点赋值为111。
当处理节点uuu时，对其所有后继vvv，更新val[v]=max⁡(val[v],val[u]+1)val[v] = \max(val[v], val[u] + 1)val[v]=max(val[v],val[u]+1)。
这实际上是在DAG\texttt{DAG}DAG（有向无环图）上求最长路径，路径长度即为该节点的最小赋值。

2. 检测矛盾

如果图中存在环（例如a > b, b > c, c > a），则无法满足所有不等式，输出-1。环的检测可以通过拓扑排序实现：如果最终处理过的节点数少于图中总节点数，说明存在环。

3. 表达式解析与求值

我们可以使用递归下降解析，根据文法：

<expression> = <term> { '+' <term> } <term> = <factor> { '*' <factor> } <factor> = '(' <expression> ')' | <variable>

解析时构建一个语法树，每个节点可以是变量、加法或乘法。求值时，将变量节点替换为对应的数值，然后递归计算子树的值。

4. 整体流程

读入表达式，解析并构建语法树，同时收集所有出现的变量。
读入不等式，根据x > y建立有向边y→xy \to xy→x，并统计入度。
对出现的变量进行拓扑排序，得到每个变量的最小赋值。若发现有环，输出-1。
用得到的赋值对语法树求值，输出结果。

5. 复杂度分析

表达式长度≤300\le 300≤300，递归解析复杂度为O(L)O(L)O(L)。
变量最多262626个，不等式最多400400400个，拓扑排序复杂度为O(V+E)O(V + E)O(V+E)，完全可行。
每个测试用例整体复杂度约为O(L+E)O(L + E)O(L+E)。

代码实现

// Evaluate the Expression// UVa ID: 11724// Verdict: Accepted// Submission Date: 2026-06-03// UVa Run Time: 0.000s//// 版权所有（C）2026，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;// 表达式节点类型enumNodeType{VAR,ADD,MUL};structExprNode{NodeType type;charvar;// 当 type == VAR 时有效ExprNode*left,*right;// 当 type == ADD 或 MUL 时有效ExprNode(charv):type(VAR),var(v),left(nullptr),right(nullptr){}ExprNode(NodeType t,ExprNode*l,ExprNode*r):type(t),left(l),right(r),var(0){}};// 解析表达式（递归下降）ExprNode*parseExpr(conststring&s,int&pos);ExprNode*parseTerm(conststring&s,int&pos);ExprNode*parseFactor(conststring&s,int&pos);ExprNode*parseExpr(conststring&s,int&pos){ExprNode*node=parseTerm(s,pos);while(pos<(int)s.size()&&s[pos]=='+'){pos++;// 跳过 '+'ExprNode*right=parseTerm(s,pos);node=newExprNode(ADD,node,right);}returnnode;}ExprNode*parseTerm(conststring&s,int&pos){ExprNode*node=parseFactor(s,pos);while(pos<(int)s.size()&&s[pos]=='*'){pos++;// 跳过 '*'ExprNode*right=parseFactor(s,pos);node=newExprNode(MUL,node,right);}returnnode;}ExprNode*parseFactor(conststring&s,int&pos){if(s[pos]=='('){pos++;// 跳过 '('ExprNode*node=parseExpr(s,pos);pos++;// 跳过 ')'returnnode;}else{// 变量returnnewExprNode(s[pos++]);}}// 收集表达式中的所有变量voidcollectVars(ExprNode*root,set<char>&vars){if(root->type==VAR){vars.insert(root->var);}else{collectVars(root->left,vars);collectVars(root->right,vars);}}// 计算表达式的值intevalExpr(ExprNode*root,map<char,int>&val){if(root->type==VAR)returnval[root->var];intleftVal=evalExpr(root->left,val);intrightVal=evalExpr(root->right,val);if(root->type==ADD)returnleftVal+rightVal;elsereturnleftVal*rightVal;}// 释放表达式树内存voidfreeExpr(ExprNode*root){if(root->type!=VAR){freeExpr(root->left);freeExpr(root->right);}deleteroot;}intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);intT;cin>>T;cin.ignore();// 忽略换行for(intcaseNum=1;caseNum<=T;++caseNum){string expr;getline(cin,expr);intI;cin>>I;cin.ignore();// 建图：graph[u] 表示 u 大于哪些节点vector<vector<char>>graph(26);vector<int>indeg(26,-1);// -1 表示该变量未出现set<char>varsSet;// 先收集表达式中的变量intpos=0;ExprNode*root=parseExpr(expr,pos);collectVars(root,varsSet);for(charv:varsSet)indeg[v-'a']=0;boolconsistent=true;for(inti=0;i<I;++i){string line;getline(cin,line);if(!consistent)continue;charx=line[0],y=line[2];// x > y => y -> x (x 至少是 y+1)// 但注意：x 和 y 必须出现在表达式中，题目保证如此if(indeg[x-'a']==-1||indeg[y-'a']==-1)continue;graph[y-'a'].push_back(x);indeg[x-'a']++;}// 拓扑排序求最小赋值queue<char>q;map<char,int>val;for(charv:varsSet){if(indeg[v-'a']==0){q.push(v);val[v]=1;}}intprocessed=0;while(!q.empty()){charu=q.front();q.pop();processed++;for(charv:graph[u-'a']){// v 至少比 u 大 1val[v]=max(val[v],val[u]+1);indeg[v-'a']--;if(indeg[v-'a']==0)q.push(v);}}if(processed!=(int)varsSet.size()){consistent=false;}if(!consistent){cout<<"Case "<<caseNum<<": -1\n";}else{intresult=evalExpr(root,val);cout<<"Case "<<caseNum<<": "<<result<<"\n";}freeExpr(root);}return0;}