UVa 727 Equation-平芜编程栈

题目描述

编写程序将中缀表达式转换为后缀表达式。输入格式特殊：每个字符（数字、运算符、括号）单独占一行，表达式之间由空行分隔。运算符仅包含+、-、*、/，操作数为单个数字。*和/优先级高于+和-，同一优先级从左到右结合。括号可改变优先级。每个测试用例是一个语法正确的表达式。

输入格式

第一行为一个整数NNN，表示测试用例个数。随后有一个空行。接下来是NNN个中缀表达式，每个表达式由若干行组成，每行一个字符（数字、运算符或括号），表达式结束时跟一个空行。

输出格式

对于每个表达式，输出一行后缀表达式（所有字符连续，无空格）。不同表达式的输出之间用一个空行分隔。

样例输入

1 3 + 2 ) * 5

样例输出

32+5*

题目分析

中缀转后缀是经典的栈应用问题。算法遍历中缀表达式，数字直接输出，左括号入栈，右括号则弹出栈中运算符直到左括号，运算符则根据优先级决定是否弹出栈顶运算符。优先级规则：*和/最高，+和-最低，同级左结合，即当当前运算符优先级不高于栈顶运算符时，弹出栈顶。最终弹出栈中剩余运算符。

解题思路

采用显式栈存储运算符。对于每个输入字符ccc：

若ccc为数字（0-9），则直接输出。
若ccc为左括号(，则入栈。
若ccc为右括号)，则不断弹出栈顶运算符并输出，直到遇到左括号，然后将左括号弹出（不输出）。
若ccc为其他运算符（+、-、*、/），则当栈非空且栈顶不是左括号且当前运算符优先级不超过栈顶运算符优先级时，弹出栈顶并输出；重复此过程后将当前运算符入栈。

遍历结束后，将栈中剩余运算符依次弹出并输出。

由于输入将每个字符单独一行，可逐行读取，遇到空行表示表达式结束。读取NNN后先忽略第一个空行，然后对每个表达式循环读取非空行并拼接，直到空行，再调用转换函数。

代码实现

// Equation// UVa ID: 727// Verdict: Accepted// Submission Date: 2016-11-29// UVa Run Time: 0.000s//// 版权所有（C）2016，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;// 定义运算符的优先级顺序，值越高，优先级越高。在栈中，括号的优先级最小。map<char,int>priority={{'+',1},{'-',1},{'*',2},{'/',2},{'(',0},{')',0}};// 比较运算符在栈中的优先级顺序。boollessPriority(charprevious,charnext){returnpriority[previous]<=priority[next];}// 将中缀表达式转换为后缀表达式。stringtoPostfix(string infix){stack<char>operands;// 操作数栈stack<char>operators;// 运算符栈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()){postfix=operands.top()+postfix;operands.pop();}returnpostfix;}intmain(intargc,char*argv[]){intcases=0;cin>>cases;cin.ignore(1024,'\n');string line;getline(cin,line);for(intc=1;c<=cases;c++){if(c>1)cout<<'\n';string infix;while(getline(cin,line),line.length()>0)infix+=line;cout<<toPostfix(infix)<<'\n';}return0;}