UVa 727 Equation

题目描述编写程序将中缀表达式转换为后缀表达式。输入格式特殊每个字符数字、运算符、括号单独占一行表达式之间由空行分隔。运算符仅包含、-、*、/操作数为单个数字。*和/优先级高于和-同一优先级从左到右结合。括号可改变优先级。每个测试用例是一个语法正确的表达式。输入格式第一行为一个整数NNN表示测试用例个数。随后有一个空行。接下来是NNN个中缀表达式每个表达式由若干行组成每行一个字符数字、运算符或括号表达式结束时跟一个空行。输出格式对于每个表达式输出一行后缀表达式所有字符连续无空格。不同表达式的输出之间用一个空行分隔。样例输入1 3 2 ) * 5样例输出325*题目分析中缀转后缀是经典的栈应用问题。算法遍历中缀表达式数字直接输出左括号入栈右括号则弹出栈中运算符直到左括号运算符则根据优先级决定是否弹出栈顶运算符。优先级规则*和/最高和-最低同级左结合即当当前运算符优先级不高于栈顶运算符时弹出栈顶。最终弹出栈中剩余运算符。解题思路采用显式栈存储运算符。对于每个输入字符ccc若ccc为数字0-9则直接输出。若ccc为左括号(则入栈。若ccc为右括号)则不断弹出栈顶运算符并输出直到遇到左括号然后将左括号弹出不输出。若ccc为其他运算符、-、*、/则当栈非空且栈顶不是左括号且当前运算符优先级不超过栈顶运算符优先级时弹出栈顶并输出重复此过程后将当前运算符入栈。遍历结束后将栈中剩余运算符依次弹出并输出。由于输入将每个字符单独一行可逐行读取遇到空行表示表达式结束。读取NNN后先忽略第一个空行然后对每个表达式循环读取非空行并拼接直到空行再调用转换函数。代码实现// Equation// UVa ID: 727// Verdict: Accepted// Submission Date: 2016-11-29// UVa Run Time: 0.000s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;// 定义运算符的优先级顺序值越高优先级越高。在栈中括号的优先级最小。mapchar,intpriority{{,1},{-,1},{*,2},{/,2},{(,0},{),0}};// 比较运算符在栈中的优先级顺序。boollessPriority(charprevious,charnext){returnpriority[previous]priority[next];}// 将中缀表达式转换为后缀表达式。stringtoPostfix(string infix){stackcharoperands;// 操作数栈stackcharoperators;// 运算符栈for(autoc:infix){// 如果是数字直接压入操作数栈中。if(isdigit(c)){operands.push(c);continue;}// 如果是左括号直接压入运算符栈中。if(c(){operators.push(c);continue;}// 如果是右括号。if(c)){// 弹出运算符栈顶元素直到遇到左括号。while(!operators.empty()operators.top()!(){operands.push(operators.top());operators.pop();}// 操作符堆栈不为空继续弹出匹配的左括号。if(!operators.empty())operators.pop();continue;}// 如果是非括号运算符当运算符堆栈为空或者运算符堆栈栈顶元素// 为左括号或者比运算符堆栈栈顶运算符的优先级高将当前运算符// 压入运算符堆栈。if(operators.empty()||operators.top()(||!lessPriority(c,operators.top())){operators.push(c);}else{// 当运算符的优先级比运算符堆栈栈顶元素的优先级低或相等时// 弹出运算符堆栈栈顶元素直到运算符堆栈为空或者遇到比// 当前运算符优先级低的运算符时结束。while(!operators.empty()lessPriority(c,operators.top())){operands.push(operators.top());operators.pop();}// 将当前运算符压入运算符堆栈。operators.push(c);}}// 当中缀表达式处理完毕运算符堆栈不为空时逐个弹出压入到操作数堆栈中。while(!operators.empty()){operands.push(operators.top());operators.pop();}// 获取操作数堆栈中保存的后缀表达式注意栈中保存的是从左至右的顺序但// 从栈中弹出时是从右至左的顺序需要适当调整。string postfix;while(!operands.empty()){postfixoperands.top()postfix;operands.pop();}returnpostfix;}intmain(intargc,char*argv[]){intcases0;cincases;cin.ignore(1024,\n);string line;getline(cin,line);for(intc1;ccases;c){if(c1)cout\n;string infix;while(getline(cin,line),line.length()0)infixline;couttoPostfix(infix)\n;}return0;}总结本题是中缀转后缀的模板题利用栈处理运算符优先级和括号。关键点在于正确比较优先级并在左结合时弹出栈顶。输入格式特殊需逐行读取并识别空行作为表达式终结。时间复杂度O(n)O(n)O(n)空间复杂度O(n)O(n)O(n)其中nnn为表达式长度。该解法清晰且高效适用于类似表达式转换问题。