题目描述根据给定的BNF\texttt{BNF}BNF文法一个数学表达式由变量小写字母a到z、运算符和*以及括号()组成运算遵循常规的优先级规则括号优先乘法优先于加法。要求给每个变量赋一个正整数使得在满足所有给定的不等式约束例如a b表示aaa必须严格大于bbb的前提下表达式的值最小。若不等式矛盾输出-1。题目分析本题包含三个主要难点表达式解析需要按照优先级正确解析含有括号、加法和乘法的表达式并能够替换变量值后求值。变量约束建模每个不等式x y表示xxx的取值必须严格大于yyy的取值。由于所有变量都取正整数这个关系可以转化为x≥y1x \ge y 1x≥y1。最小化赋值为了使表达式结果最小应让每个变量的取值尽可能小同时满足所有不等式。这等价于在有向图中求出每个节点的最小可能值。解题思路1. 将不等式转化为有向图考虑不等式x y因为变量都是正整数所以等价于x≥y1x \ge y 1x≥y1。我们可以建一个有向图从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(VE)O(V E)O(VE)完全可行。每个测试用例整体复杂度约为O(LE)O(L E)O(LE)。代码实现// Evaluate the Expression// UVa ID: 11724// Verdict: Accepted// Submission Date: 2026-06-03// UVa Run Time: 0.000s//// 版权所有C2026邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;// 表达式节点类型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(conststrings,intpos);ExprNode*parseTerm(conststrings,intpos);ExprNode*parseFactor(conststrings,intpos);ExprNode*parseExpr(conststrings,intpos){ExprNode*nodeparseTerm(s,pos);while(pos(int)s.size()s[pos]){pos;// 跳过 ExprNode*rightparseTerm(s,pos);nodenewExprNode(ADD,node,right);}returnnode;}ExprNode*parseTerm(conststrings,intpos){ExprNode*nodeparseFactor(s,pos);while(pos(int)s.size()s[pos]*){pos;// 跳过 *ExprNode*rightparseFactor(s,pos);nodenewExprNode(MUL,node,right);}returnnode;}ExprNode*parseFactor(conststrings,intpos){if(s[pos](){pos;// 跳过 (ExprNode*nodeparseExpr(s,pos);pos;// 跳过 )returnnode;}else{// 变量returnnewExprNode(s[pos]);}}// 收集表达式中的所有变量voidcollectVars(ExprNode*root,setcharvars){if(root-typeVAR){vars.insert(root-var);}else{collectVars(root-left,vars);collectVars(root-right,vars);}}// 计算表达式的值intevalExpr(ExprNode*root,mapchar,intval){if(root-typeVAR)returnval[root-var];intleftValevalExpr(root-left,val);intrightValevalExpr(root-right,val);if(root-typeADD)returnleftValrightVal;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;cinT;cin.ignore();// 忽略换行for(intcaseNum1;caseNumT;caseNum){string expr;getline(cin,expr);intI;cinI;cin.ignore();// 建图graph[u] 表示 u 大于哪些节点vectorvectorchargraph(26);vectorintindeg(26,-1);// -1 表示该变量未出现setcharvarsSet;// 先收集表达式中的变量intpos0;ExprNode*rootparseExpr(expr,pos);collectVars(root,varsSet);for(charv:varsSet)indeg[v-a]0;boolconsistenttrue;for(inti0;iI;i){string line;getline(cin,line);if(!consistent)continue;charxline[0],yline[2];// x y y - x (x 至少是 y1)// 但注意x 和 y 必须出现在表达式中题目保证如此if(indeg[x-a]-1||indeg[y-a]-1)continue;graph[y-a].push_back(x);indeg[x-a];}// 拓扑排序求最小赋值queuecharq;mapchar,intval;for(charv:varsSet){if(indeg[v-a]0){q.push(v);val[v]1;}}intprocessed0;while(!q.empty()){charuq.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()){consistentfalse;}if(!consistent){coutCase caseNum: -1\n;}else{intresultevalExpr(root,val);coutCase caseNum: result\n;}freeExpr(root);}return0;}