PAT 解题报告 (数据结构学习与实验指导) 3-06. 表达式转换

3-06. 表达式转换题目描述:

算术表达式有前缀表示法、中缀表示法和后缀表示法等形式。日常使用的算术表达式是采用中缀表示法,即二元运算符位于两个运算数中间。请设计程序将中缀表达式转换为后缀表达式。

3-06. 表达式转换算法分析:

中缀转成后缀的算法:  从左到右遍历中缀表达式的每个数字和符号,若是数字就输出(比较中缀, 后缀表达式, 他们的操作数的顺序都是不变的);若是符号,则判断其与栈顶符号的优先级,是右括号或优先级低于栈顶符号则栈顶元素依次出栈并输出,并将当前符号进栈 (先出栈的计算后缀表达式的时候先使用, 先计算, 先计算的也就是优先级高的, 所以这一条应该是非常自然的一条),重复此过程, 一直到最终输出后缀表达式为止。另外如果是右括号, 则一直出栈出栈, 总是到左括号为止. 可以AC的源代码如下:

#include <stack>
#include <string>
#include <iostream>
#include <vector>

void doPrint(const std::vector<std::string> &vecTokens) {
	int iLen = vecTokens.size();
	for(int i = 0; i < iLen; ++i) {
		if(i) std::cout << ' ' << vecTokens[i];
		else std::cout << vecTokens[i];
	}
	std::cout << std::endl;
	return ;
}

bool isOperator(char c) {
	switch(c) {
	case '+':
	case '-':
	case '*':
	case '/':
	case '(':
	case ')':
		return true;
	}
	return false;
}

std::string eatFirstOperand(int *pPositon, const std::string &strInput) {
	int iStart = *pPositon;
	if('+' == strInput[iStart]) {
		++iStart;
		++*pPositon;
	}
	if('-' == strInput[iStart]) {
		++*pPositon;
	}
	while(*pPositon < strInput.size() && !isOperator(strInput[*pPositon]))
		++(*pPositon);
	return strInput.substr(iStart, *pPositon - iStart);
}

void gao(const std::string &strInput) {
	std::vector<std::string> vecResult;
	int iLen = strInput.size();
	std::stack<char> stkOperators;
	int iPos = 0;
	while(iPos < iLen) {
		if(isOperator(strInput[iPos])) {
			switch (strInput[iPos])
			{
			case '+':
			case '-':
				if(0 == iPos || '(' == strInput[iPos - 1]) {
					vecResult.push_back(eatFirstOperand(&iPos, strInput));
					continue;
				}
				while(!stkOperators.empty() && stkOperators.top() != '(') {
					std::string strOperator("");
					strOperator.push_back(stkOperators.top());
					stkOperators.pop();
					vecResult.push_back(strOperator);
				}
				stkOperators.push(strInput[iPos]);
				break;
			case ')':
				while(stkOperators.top() != '(') {
					std::string strOperator("");
					strOperator.push_back(stkOperators.top());
					stkOperators.pop();
					vecResult.push_back(strOperator);
				}
				stkOperators.pop();
				break;
			case '*':
			case '/':
			case '(':
				stkOperators.push(strInput[iPos]);
				break;
			default:
				break;
			}
			++iPos;
		}
		else {
			vecResult.push_back(eatFirstOperand(&iPos, strInput));
		}
	}
	while(!stkOperators.empty()) {
		std::string strOperator("");
		strOperator.push_back(stkOperators.top());
		stkOperators.pop();
		vecResult.push_back(strOperator);
	}
	doPrint(vecResult);
	return ;
}

int main() {
	std::string strInput;
	std::cin >> strInput;
	gao(strInput);
	return 0;
}

3-06. 表达式转换注意点:

这里的算法并没有处理错误情况, 都是假设输入是合法的中缀表达式, 中缀转成后缀的算法应该是常规算法, 不难, 这里特别要注意的数判断+/-有可能只是正数负数的符号表示而不是操作符, 这里的区分对待是比较tricky的地方, 还有注意括号的处理, 考虑这个例子: ((((((7))))))转换以后应该输出一个7并且左对齐.

Written on April 19, 2014