PAT 解题报告 (数据结构学习与实验指导) 3-07. 求前缀表达式的值

3-07. 求前缀表达式的值题目描述:

算术表达式有前缀表示法、中缀表示法和后缀表示法等形式。前缀表达式指二元运算符位于两个运算数之前,例如2+3*(7-4)+8/4的前缀表达式是:+ + 2 * 3 – 7 4 / 8 4。请设计程序计算前缀表达式的结果值。

3-07. 求前缀表达式的值算法分析:

计算前缀表达式和计算后缀表达式基本上是一样的算法, 都是利用栈, 遇到操作数就压栈, 遇到操作符就把栈顶的两个元素出栈, 然后做计算, 只是对于有顺序的运算符号来讲(copyright @sigmainfy)两个操作数的位置不一样, 比如7 – 4的前缀表达式是- 7 4, 那么从右边4是第一个压栈的, 7是第二个压栈的, 遇到-的时候, 7第一个出栈, 作为被减数, 也就是对于前缀表达式来讲, 讲栈顶两个元素出栈的时候使用第一个元素作为被减数/被除数; 在看7 – 4的后缀表达式是7 4 -, 从左边开始7 是第一个进栈的, 然后4是第一个出栈的, 所以对于后缀表达式来讲, 将栈顶的两个元素出栈的时候使用第二个元素作为被减数/被除数. 下面是可以AC的代码:

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

int getType(const std::string &strToken)
{
	int iLen = strToken.size();

	if(iLen > 1)
		return TYPE_OPERAND;
	if(iLen == 1) {
		switch (strToken[0])
		{
			case '+':
			case '-':
			case '*':
			case '/':
				return TYPE_OPERATOR;
			default:
				if(strToken[0] >= '0' && strToken[0] <= '9')
					return TYPE_OPERAND;
				return TYPE_INVALID;
		}
	}
	return TYPE_INVALID;
}

double calc(double value1, double value2, char op)
{
	if('+' == op)
		return value1 + value2;
	if('-' == op)
		return value1 - value2;
	if('*' == op)
		return value1 * value2;
	if('/' == op) {
		if(0 == value2)
			throw ERROR_ARITHMETIC;
		return value1 / value2;
	}
	throw ERROR_UNDEFINED;
}

double calcPrefixValue2(const std::vector<std::string> &vecTokens)
{
	std::stack<double> stk;
	int iLen = vecTokens.size();
	for(int i = iLen - 1; i >= 0; --i) {
		int iType = getType(vecTokens[i]);
		if(TYPE_OPERAND == iType) {
			stk.push(atof(vecTokens[i].c_str()));
		}
		if(TYPE_OPERATOR == iType) {
			if(stk.size() <= 1)
				throw ERROR_INVALID_OPERATION;
			double op1 = stk.top(); stk.pop();
			double op2 = stk.top(); stk.pop();
			stk.push(calc(op1, op2, vecTokens[i][0]));
		}
		if(TYPE_INVALID == iType) {
			throw ERROR_INVALID_OPERATION;
		}
	}
	if(stk.size() != 1)
		throw ERROR_STK_WRONG_SIZE;
	return stk.top();
}

int main()
{
	std::string strInput;
	std::vector<std::string> vecTokens;

	while(std::cin >> strInput)
		vecTokens.push_back(strInput);
	try {
		double dRet = calcPrefixValue2(vecTokens);
		printf("%.1lf\n", dRet);
	}
	catch(int iException) {
		printf("ERROR\n");
	}
	return 0;
}

3-07. 求前缀表达式的值注意点(发散知识点):

上面的程序并没有做输入的合法性检查, 比如如果输入里面有不合法的操作数, 程序可能会蹦, 但是测试用例里面应该没有这类的test case. 因为要检测合法的操作数相当于另一个独立的比较麻烦的逻辑.

另一点, 表面上, 或者直接从名字来看, 有一个很诱人的想法把前缀表达式转换成后缀表达式是不是只需要reverse前缀表达式就可以了? 仔细想一想显然不是的, 比如例子(7 – 1) * 3, 前缀表达式就是* – 7 1 3, 后缀表达式就是7 1 – 3 *, 明显不是反转的关系. 在深入想想, 其实无论是前缀, 中缀还是后缀表达式, 记住他们的操作数的顺序都是一样的就可以了, 所以根据这一点, 也知道, 前缀转后缀不是简单的反转一下就可以了。 至于具体如何进行前缀表达式和后缀表达式之前的转换, 大家可以思考一下?

(全文完,原创文章,转载时请注明作者和出处)


(转载本站文章请注明作者和出处 烟客旅人 sigmainfy — http://www.sigmainfy.com,请勿用于任何商业用途)

Written on April 20, 2014