UVa 198 Peter‘s Calculator-开发者社区

题目分析

Peter\texttt{Peter}Peter需要一个支持整数运算的计算器，功能包括：

变量赋值，变量名由字母开头，后跟至多494949个字母或数字
支持加法、减法、乘法运算
表达式可以引用尚未定义的变量
PRINT\texttt{PRINT}PRINT指令输出变量的值，若变量未定义或存在循环依赖则输出UNDEF\texttt{UNDEF}UNDEF
RESET\texttt{RESET}RESET指令清空所有变量定义

变量是否未定义的判定条件：

变量从未被赋值
变量的定义中引用了未定义的变量
变量的定义中存在循环依赖

解题思路

本题的核心是处理带依赖关系的表达式求值。由于变量可以相互引用，且存在循环依赖的可能，需要在求值时检测循环。

整体框架

解析输入：每行可能是赋值、打印或重置指令
表达式解析：将中缀表达式转换为后缀表达式（逆波兰表示），方便后续计算
循环检测：在递归求值时，使用集合记录当前求值路径上的变量，若重复出现则检测到循环
延迟求值：变量被赋值时只存储其后缀表达式，实际求值在PRINT\texttt{PRINT}PRINT时进行

关键实现细节

1. 负数的处理

题目中的数字可以以负号开头（如−5-5−5）。解析时，将负号特殊标记（代码中用_代替），与减法运算符区分开。

判断条件：当-的前一个是运算符、括号或行首时，表示负数而非减法。

2. 中缀转后缀

使用调度场算法（Shunting-yard algorithm\texttt{Shunting-yard algorithm}Shunting-yard algorithm），定义优先级：

+、-：优先级111
*：优先级222
(、)：优先级000

3. 后缀表达式求值与循环检测

递归求值时，维护一个全局集合undefined记录当前求值路径上的变量：

进入求值某个变量时，将其加入集合
若求值中再次遇到集合内的变量，说明存在循环依赖，返回失败
求值完成后从集合中移除

代码实现

// Peter's Calculator// UVa ID: 198// Verdict: Accepted// Submission Date: 2016-03-17// UVa Run Time: 0.000s//// 版权所有（C）2016，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;constintVARIABLE=0,OPERATOR=1,NUMBER=2;// 符号结构体：存储表达式中每个元素的信息structsymbol{string token;// 符号的字符串表示（变量名/运算符/数字字符串）intoperand;// 若为数字类型，存储其整数值intcategory;// 类型：VARIABLE（变量）、OPERATOR（运算符）、NUMBER（数字）};set<string>undefined;// 用于循环检测，记录当前求值路径上的变量map<string,vector<symbol>>formula;// 存储每个变量对应的后缀表达式map<string,int>priority;// 存储运算符的优先级// 递归计算后缀表达式的值// symbols: 后缀表达式序列// value: 输出参数，用于存储计算结果// 返回值: true表示计算成功，false表示变量未定义或存在循环依赖boolcalculate(vector<symbol>symbols,int&value){stack<symbol>operands;// 操作数栈for(inti=0;i<symbols.size();i++){symbol s=symbols[i];// 变量或数字直接入栈if(s.category==VARIABLE||s.category==NUMBER)operands.push(s);else{// 遇到运算符，弹出两个操作数symbol b=operands.top();operands.pop();symbol a=operands.top();operands.pop();intaa,bb,cc;// 处理左操作数 aif(a.category==VARIABLE){if(undefined.count(a.token)>0)returnfalse;if(formula.count(a.token)==0)returnfalse;undefined.insert(a.token);if(calculate(formula[a.token],aa)==false)returnfalse;undefined.erase(a.token);}elseaa=a.operand;// 处理右操作数 bif(b.category==VARIABLE){if(undefined.count(b.token)>0)returnfalse;if(formula.count(b.token)==0)returnfalse;undefined.insert(b.token);if(calculate(formula[b.token],bb)==false)returnfalse;undefined.insert(b.token);}elsebb=b.operand;// 执行运算if(s.token=="+")cc=aa+bb;elseif(s.token=="-")cc=aa-bb;elseif(s.token=="*")cc=aa*bb;// 将运算结果作为数字压入栈中operands.push((symbol){"",cc,NUMBER});}}// 栈顶即为最终结果if(operands.top().category==NUMBER){value=operands.top().operand;returntrue;}else{// 栈顶为变量，需要继续递归求值string variable=operands.top().token;if(undefined.count(variable)>0)returnfalse;if(formula.count(variable)==0)returnfalse;undefined.insert(variable);if(calculate(formula[variable],value))undefined.erase(variable);elsereturnfalse;}returntrue;}// 判断运算符 a 的优先级是否不高于运算符 bboollessPriority(string a,string b){returnpriority[a]<=priority[b];}// 中缀表达式转后缀表达式（逆波兰表达式）vector<symbol>infixToPostfix(vector<symbol>symbols){stack<symbol>operands,operators;// operands: 输出栈, operators: 运算符栈for(inti=0;i<symbols.size();i++){symbol s=symbols[i];// 数字或变量直接输出到 operands 栈if(s.category==NUMBER||s.category==VARIABLE)operands.push(s);else{// 左括号直接入运算符栈if(s.token=="(")operators.push(s);// 右括号：弹出运算符直到遇到左括号elseif(s.token==")"){while(!operators.empty()&&operators.top().token!="("){operands.push(operators.top());operators.pop();}// 弹出左括号if(!operators.empty())operators.pop();}else{// 当前运算符优先级高时直接入栈，否则弹出优先级较高的运算符if(operators.empty()||operators.top().token=="("||!lessPriority(s.token,operators.top().token))operators.push(s);else{while(!operators.empty()&&lessPriority(s.token,operators.top().token)){operands.push(operators.top());operators.pop();}operators.push(s);}}}}// 弹出剩余运算符while(!operators.empty()){operands.push(operators.top());operators.pop();}// 反转得到正确的后缀表达式顺序symbols.clear();while(!operands.empty()){symbols.insert(symbols.begin(),operands.top());operands.pop();}returnsymbols;}// 解析赋值语句voidparse(string line){// 删除所有空格for(inti=line.length()-1;i>=0;i--)if(isblank(line[i]))line.erase(line.begin()+i);// 分离左值和右值表达式string left=line.substr(0,line.find(":="));line=line.substr(line.find(":=")+2);// 将负数标记转换为特殊字符 '_'，以便与减法运算符区分intindex=line.length()-1;while(index>=2){if(isdigit(line[index])&&line[index-1]=='-'){if(line[index-2]=='+'||line[index-2]=='-'||line[index-2]=='('||line[index-2]=='*'){line[index-1]='_';index-=2;}}index--;}// 处理行首的负号if(line.front()=='-')line[0]='_';// 词法分析：将字符串分割为 tokenindex=0;vector<symbol>symbols;while(index<line.length()){// 处理数字（包括负数）if((line[index]>='0'&&line[index]<='9')||line[index]=='_'){intsign=line[index]=='_'?-1:1;intoperands=0;if(line[index]=='_')index++;while(index<line.length()&&(line[index]>='0'&&line[index]<='9')){operands=operands*10+line[index]-'0';index++;}symbols.push_back((symbol){"",operands*sign,NUMBER});}// 处理变量名elseif(isalpha(line[index])){string block;while(index<line.length()){if(isalpha(line[index])||isdigit(line[index])){block+=line[index];index++;}elsebreak;}symbols.push_back((symbol){block,0,VARIABLE});}// 处理运算符else{symbols.push_back((symbol){string(1,line[index]),0,OPERATOR});index++;}}// 将中缀表达式转换为后缀表达式并存储formula[left]=infixToPostfix(symbols);}intmain(){// 初始化运算符优先级priority.insert(pair<string,int>("+",1));priority.insert(pair<string,int>("-",1));priority.insert(pair<string,int>("*",2));priority.insert(pair<string,int>("(",0));priority.insert(pair<string,int>(")",0));string line;while(getline(cin,line)){// 赋值语句if(line.find(":=")!=line.npos)parse(line);else{// PRINT 语句if(line.find("PRINT")!=line.npos){// 从行尾提取要打印的变量名intindex=line.length()-1;while(isblank(line[index]))index--;string block;while(!isblank(line[index])){block+=line[index];index--;}reverse(block.begin(),block.end());// 计算并输出结果undefined.clear();if(formula.count(block)>0){undefined.insert(block);intvalue;if(calculate(formula[block],value))cout<<value<<endl;elsecout<<"UNDEF"<<endl;}elsecout<<"UNDEF"<<endl;}// RESET 语句：清空所有变量定义elseformula.clear();}}return0;}