postfixexpr.cpp

一个我的数据结构解题集合

#include <assert.h>
#include <string>
#include <sstream>
#include <stdexcept>
#include "Queue.h"
#include "Stack.h"
#include "Term.h"
#include "Parser.h"

#include "PostfixExpr.h"


namespace {		// 限制在本文件内使用

	/* 用于将表达式转化为后缀表达式的访问器
	 */
	struct PostfixConvertVisitor : public TermVisitor {
		Stack<Operator *> optrStack;	// 运算符栈
		Queue<Term *> result;			// 结果队列

		/* 访问一个运算符
		 */
		virtual
		void visitOperator(Operator& optr) {
			if ( optr.value() == Operator::RP ||
				 optr.value() == Operator::End ) {	// 遇到")"或";"
				// 将栈中到最近的"("或栈空为止的符号弹出
				while ( !optrStack.isEmpty() &&
						(optrStack.top()->value() != Operator::LP) ) {
					Operator *top = optrStack.top();
					result.push( top );
					optrStack.pop();
				}

				if ( optrStack.isEmpty() &&
					 optr.value() == Operator::End ) {	// 遇到";"且括号匹配正常
					;	// 无事可做
				} else
				if ( !optrStack.isEmpty() &&
					 optr.value() == Operator::RP ) {	// 遇到")"且找到"("与之匹配
					optrStack.pop();	// 将"("弹栈
				} else {								// 遇到";"但找到"("尚未匹配 或者
														// 遇到")"但未找到"("与之匹配
					if (PostfixExpr::PARENTHESES_CHECKED) {
						stringstream buf;
						buf << "PostfixConvertVisitor: Invalid operator\n"
							<< "\tOperation: visitOperator(Operator&)"
							<< "\tOperator: " << char(optr.value())
							<< endl;
						throw std::invalid_argument(buf.str());
					}

					/* 处理遇到";"但找到"("尚未匹配的情况
					 */
					while ( !optrStack.isEmpty() &&
							optrStack.top()->value() == Operator::LP ) {
						optrStack.pop();	// 将"("弹栈
					}
					visitOperator(Operator(';'));		// 清理剩下的符号
				} 

			} else
			if ( optr.value() == Operator::LP ) {	// 遇到"("

				optrStack.push(&optr);	// 直接进栈

			} else {	// 遇到其他运算符
				// 先将栈中的元素弹出, 直到以下条件之一被满足:
				// 1. 栈顶元素优先级小于optr的优先级
				// 2. 遇到"("
				// 3. 栈空
				// 其中, 条件2由"("的内定优先级小于所有其他运算符以及条件1保证
				while ( !optrStack.isEmpty() &&
						(optr.prec() <= optrStack.top()->prec()) ) {
					Operator *top = optrStack.top();
					result.push( top );
					optrStack.pop();
				}

				optrStack.push(&optr);	// 将optr进栈
			}
		} // visitOperator(Operator&)

		/* 访问一个操作数
		 */
		virtual
		void visitOperand(Operand& opnd) {
			result.push(&opnd);		// 马上输出
		} // visitOperand(Operand&)

		/* 访问一个变量: 转到操作数访问
		 */
		virtual
		void visitVariable(Variable& opnd) {
			visitOperand(opnd);
		} // visitVariable(Variable&)

		/* 访问一个数值: 转到操作数访问
		 */
		virtual
		void visitNumber(Number& opnd) {
			visitOperand(opnd);
		}


	}; // PostfixConvertVisitor



	/* 用于后缀表达式求值的访问器
	 */
	struct EvalPostfixExprVisitor : public TermVisitor {
		Stack<Operand *> opndStack;		// 操作数栈

		/* 访问一个运算符
		 */
		virtual
		void visitOperator(Operator& optr) {
			try {
				// 读取两个操作数, 注意弹栈为倒序
				Operand *op2 = opndStack.top();
				opndStack.pop();
				Operand *op1 = opndStack.top();
				opndStack.pop();

				// 求值
				double x = op1->getValue();
				double y = op2->getValue();
				double value;
				value = optr.eval(x, y);

				// 再次入栈
				Operand *res = new Number(value);
				opndStack.push(res);

			} catch ( const std::out_of_range& ) {	// 表达式错误导致opndStack.top()抛出异常
				stringstream buf;
				buf << "EvalPostfixExprVisitor: Invalid expression!\n"
				    << "\tReason: Operand not enough!\n"
				    << "\tOperation: visitOperator(Operator&)\n"
				    << endl;
				throw std::invalid_argument(buf.str());
			}

		} // visitOperator(Operator&)


		/* 访问一个操作数
		 */
		virtual
		void visitOperand(Operand& opnd) {
			opndStack.push(&opnd);		// 马上压栈
		} // visitOperand(Operand&)


		/* 访问一个变量: 转到操作数访问
		 */
		virtual
		void visitVariable(Variable& opnd) {
			visitOperand(opnd);
		} // visitVariable(Variable&)

		/* 访问一个数值: 转到操作数访问
		 */
		virtual
		void visitNumber(Number& opnd) {
			visitOperand(opnd);
		}

	}; // EvalPostfixExprVisitor



	/* 用于析构的访问器
	 */
	struct PostfixExprCleaner : public TermVisitor {

		/* 访问一个运算符
		 */
		virtual
		void visitOperator(Operator& optr) {
			delete &optr;
		} // visitOperator(Operator&)


		/* 访问一个操作数
		 */
		virtual
		void visitOperand(Operand& opnd) {
			assert(false);		// 不可能到达这儿
		} // visitOperand(Operand&)


		/* 访问一个变量: 转到操作数访问
		 */
		virtual
		void visitVariable(Variable& opnd) {
			// 什么也不做, 稍后清理
		} // visitVariable(Variable&)

		/* 访问一个数值: 转到操作数访问
		 */
		virtual
		void visitNumber(Number& opnd) {
			delete &opnd;
		}
	}; // PostfixExprCleaner

} // namespace



/* 将表达式expr转换为后缀表达式, 
 * 并将表达式各项保存在队列中返回
 * 参数varList用于保存表达式中的所有变量的地址, 以便日后清理
 * (除了变量, 表达式中的每个项都指向唯一的地址, 无需顾虑)
 */
PostfixExpr::PostfixExpr(string expr) {
	Parser parser(expr);
	PostfixConvertVisitor visitor;

	while ( Term *term = parser.readNext() ) {	// 分析表达式各项
		term->accept(visitor);		// 访问 (处理) 表达式各项
	}

	Operator(';').accept(visitor);	// 清理栈中的剩余元素

	varList_ = parser.getVars();	// 保存表达式中的所有变量的地址, 以便日后清理
	expr_ = visitor.result;			// 保存后缀表达式

} // PostfixExpr(string)


/* 析构函数, 清理后所占用的资源
 */
PostfixExpr::~PostfixExpr() {

	PostfixExprCleaner visitor;

	// 删除表达式各项 (除了变量)
	Term *term = 0;
	while ( !expr_.isEmpty() ) {
		term = expr_.front();
		term->accept(visitor);
		expr_.pop();
	}

	// 删除变量
	for (int i=0; i<varList_.size(); ++i) {
		delete varList_[i];
	}

} // ~PostfixExpr()




/* 打印后缀表达式q
 */
void PostfixExpr::print() const {
	Queue<Term *> q(expr_);			// 先取得后缀表达式的一份拷贝

	while ( !q.isEmpty() ) {
		cout << q.front()->toString() << ' ';
		q.pop();
	}
	cout << endl;
} // print() const


/* 求后缀表达式expr的值
 */
double PostfixExpr::eval() const {
	Queue<Term *> expr(expr_);		// 先取得后缀表达式的一份拷贝

	if ( expr.isEmpty() ) return 0.0;

	EvalPostfixExprVisitor visitor;

	Term *term = 0;
	while ( !expr.isEmpty() ) {		// 分析表达式各项
		term = expr.front();
		term->accept(visitor);		// 访问 (处理) 表达式各项
		expr.pop();
	}

	double val = visitor.opndStack.top()->getValue();
	visitor.opndStack.pop();

	if ( !visitor.opndStack.isEmpty() ) {	// 表达式有错误
		stringstream buf;
		buf << "PostfixExpr: Invalid expression!\n"
		    << "\tReason: Operator not enough!\n"
		    << "\tOperation: eval() const\n"
		    << endl;
		throw std::invalid_argument(buf.str());
	}

	return val;
} // eval() const