题目描述在ACM\texttt{ACM}ACM行星的东南部存在多种使用非标准运算符符号的方言。这些方言中加、减、乘、整数除法这四种运算分别使用不同的本地符号且它们的优先级数字越大优先级越高和结合性L左结合R右结合也各不相同。给定一个方言描述包含四个标准运算符对应的本地符号、优先级和结合性以及若干条使用该方言书写的表达式要求计算每个表达式的值并将表达式中的本地运算符替换为标准运算符、-、*、/后输出。输入格式注意在线测试数据的格式与题目描述不符以下是经过测试得到的正确的在线测试数据格式输入文件包含多组测试数据组数由第一行整数TTT给出。每组数据格式如下第一行为一个空行仅在组间存在第一组前也有一个空行。接下来444行每行是一个长度为444的字符串c1c2c3c4c_1c_2c_3c_4c1​c2​c3​c4​描述一个标准运算符的本地映射c1c_1c1​标准运算符、-、*、/之一c2c_2c2​该运算符对应的本地符号一个可见字符不含数字、括号及空白c3c_3c3​一个数字字符0~9表示该运算符的优先级c4c_4c4​一个字母L表示左结合R表示右结合。之后若干行每行一个使用本地符号书写的表达式不含空白字符表达式可包含数字、括号以及上述四个本地符号。表达式以空行结束即下一行为空行表示该组数据结束。输入以EOF\texttt{EOF}EOF结束。输出格式对于每个输入表达式输出一行内容为将本地运算符替换为标准运算符后的表达式后跟一个空格、一个等号、一个空格以及该表达式的计算结果。每组内的表达式连续输出组间由一个空行分隔。样例输入2 1L -#3R *$2L /%2L 12#3 (12)#3 34#5$6 *1L -2L *#3R /$4L 1*2*3 12#3*4 10$3*2输出12-3 0 (12)-3 0 34-5*6 -3 123 6 1-2*34 -1 10/32 5题目分析本题的核心是实现一个能够处理自定义优先级和结合性的表达式求值器。与常规算术表达式不同这里运算符的优先级数字0∼90 \sim 90∼9和结合性左/右由输入动态指定且必须严格遵循相同运算符重复时按其自身结合性左或右进行结合。不同运算符即使优先级相同一律按从左到右的顺序执行。这意味着我们不能使用标准的中缀转后缀算法如调度场算法因为调度场算法通常预设同优先级运算符具有相同的结合性例如和-都是左结合而本题中不同运算符可能拥有不同的结合性但同优先级不同运算符之间却强制左结合。同时表达式可能包含括号需要正确处理括号内的子表达式。解题思路递归下降解析器我们采用优先级爬升Pratt Parser\texttt{Pratt Parser}Pratt Parser的递归下降解析方法。定义一个解析函数parseExpr(minPrec)它解析一个表达式其中minPrec表示当前允许的最低优先级。函数返回一个Node结构包含表达式的计算结果val以及对应的标准运算符表达式字符串stdExpr。解析过程如下解析基本单元parsePrimary若当前字符为(则递归调用parseExpr(0)解析括号内的内容遇到)后结束返回内部节点的值。否则读取连续的数字字符返回其整数值。处理运算符在parseExpr中先获得左部表达式left。然后循环检查当前字符是否为已定义的本地运算符。若是则获取其优先级prec和结合性assoc。根据结合性决定是否停止结合当前运算符若为左结合L当prec minPrec时停止若为右结合R当prec minPrec时停止。如果不需要停止则消费该运算符递归解析右部表达式传入的minPrec为左结合时传prec 1右结合时传prec。然后计算左部和右部结果生成标准表达式字符串更新left为新节点。该算法通过调整递归调用时的minPrec参数有效地控制了运算符的结合顺序左结合运算符要求右侧表达式的优先级必须大于当前优先级即prec1从而保证同优先级的运算符不会被右侧吸收右结合运算符则允许右侧表达式包含相同优先级的运算符即prec从而形成右结合。输出每个Node在计算过程中同时生成对应的标准表达式字符串合并左右子表达式和当前标准运算符最终根节点的stdExpr即为转换后的完整表达式。正确性说明递归下降解析器严格按照优先级和结合性规则构造语法树每次结合运算符时都正确限制了右侧子表达式的优先级范围。括号通过parsePrimary中的递归调用优先处理符合括号最高优先级的惯例。最终生成的表达式字符串与计算结果一致。复杂度分析设表达式长度为LLL。递归下降解析过程中每个字符至多被访问一次数字可能连续读取因此单次表达式求值的时间复杂度为O(L)O(L)O(L)。空间复杂度为递归调用栈深度最坏情况下为O(L)O(L)O(L)深层嵌套括号可接受。对于多组测试数据总时间复杂度为O(∑L)O(\sum L)O(∑L)其中∑L\sum L∑L为所有表达式长度之和。代码实现由于在线测试数据的输出可能存在问题导致本题难以通过。// Crazy Calculator// UVa ID: 354// Verdict: Wrong Answer// Submission Date: 2026-06-21// UVa Run Time: 0.070s//// 版权所有C2026邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;unordered_mapchar,charlocalToStd;// 本地符号 - 标准运算符unordered_mapchar,intlocalPrec;// 本地符号 - 优先级unordered_mapchar,charlocalAssoc;// 本地符号 - 结合性structNode{intval;string stdExpr;};// 函数原型声明intapplyOp(inta,intb,charstdOp);NodeparsePrimary();NodeparseExpr(intminPrec);string expr;intpos,n;intapplyOp(inta,intb,charstdOp){switch(stdOp){case:returnab;case-:returna-b;case*:returna*b;case/:return(b0)?0:a/b;}return0;}NodeparsePrimary(){if(posnexpr[pos](){pos;// 跳过 (Node innerparseExpr(0);if(posnexpr[pos]))pos;return{inner.val,(inner.stdExpr)};}else{intnum0;while(posnisdigit(expr[pos])){numnum*10(expr[pos]-0);pos;}return{num,to_string(num)};}}NodeparseExpr(intminPrec){Node leftparsePrimary();while(posnlocalToStd.find(expr[pos])!localToStd.end()){charopexpr[pos];intpreclocalPrec[op];charassoclocalAssoc[op];if((assocLprecminPrec)||(assocRprecminPrec))break;pos;// 消费运算符Node rightparseExpr((assocL)?prec1:prec);intresapplyOp(left.val,right.val,localToStd[op]);string stdExprleft.stdExprlocalToStd[op]right.stdExpr;left{res,stdExpr};}returnleft;}intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);string line;getline(cin,line);intTstoi(line);getline(cin,line);// 空行for(intcs0;csT;cs){if(cs)cout\n;localToStd.clear();localPrec.clear();localAssoc.clear();for(intk0;k4;k){getline(cin,line);charstdOpline[0];charlocalSymline[1];intprecline[2]-0;charassocline[3];localToStd[localSym]stdOp;localPrec[localSym]prec;localAssoc[localSym]assoc;}while(getline(cin,line)){if(line.empty())break;exprline;pos0;nexpr.size();Node rootparseExpr(0);coutroot.stdExpr root.val\n;}}return0;}