infix2postfix.h

C++数据结构的例子

/*这个类通过栈实现算法，这个类把中缀表达式，转换成的后缀表达式
及expressionSymbol对象的栈作为私有成员*/
#include<iostream>
#include<string>
#include<stack>
#include<ctype.h>
#include<exception>
#include"expressionSybol.h"
using namespace std;

class infix2Postfix
{
public:
	infix2Postfix();//中缀表达式默认为空
	void setInfixExp(const string& infixExp);//改变中缀表达式
	string postfix();//返回包含等效、后缀表达式的字符串
	void expressionError(string& str);
private:
	string infixExpression;//中缀表达式
	string postExpression;//后缀表达式
	stack<expressionSymbol> operatorStack;//expressionSymbol对象的栈
	void outputHigherOrEqual(const expressionSymbol& op);
	//op保存当前符号，只要栈顶的符号的栈优先机大于或等于当前的输入优先级，则出栈并输出
	bool isOperator(char ch)const;
};

infix2Postfix::infix2Postfix()
{
	infixExpression=" ";
}

void infix2Postfix:: setInfixExp(const string& infixExp)
{
	infixExpression=infixExp;
}

void infix2Postfix::expressionError(string& str) throw (exception)
{
	cout<<str<<endl;
}


void infix2Postfix::outputHigherOrEqual(const expressionSymbol& op)
{
	expressionSymbol op2;
	while(!operatorStack.empty () && (op2=operatorStack.top()) >= op)
	{
		operatorStack.pop();
		postExpression+=op2.getOp ();
		postExpression+=' ';
	}
}

string infix2Postfix::postfix ()
{
	expressionSymbol op;
	int rank=0;//等级
	char ch;

	if(isdigit(ch))
	{
		postExpression+=ch;//只将运算数加到输出表达式中
		postExpression+=' ';
		rank++;//运算数的等级为1
		if(rank>1)
			throw
				expressionError("infix2Postfix: Operator expected");
	}
	else if(isOperator(ch) || ch=='(')
	{
		if(ch != '(')//左括号的等级为-1
			rank--;
		if(rank<0)
			throw
				expressionError("infix2Postfix: Operand expected");
		else
		{
			op=expressionSymbol(ch);
			outputHigherOrEqual(op);
			operatorStack.push (op);
		}
	}
	else if(ch==')')
	{
		op=expressionSymbol(ch);//生成一个expressionSymbol对象容纳‘）’，它的优先级为0
	//低于任何除左括号的运算符，将子表达式的运算符出栈直至遇到作括号
		outputHigherOrEqual(op);
		if(operatorStack.empty ())
			throw
				expressionError("infix2Postfix: Missing '(' ");
		else
			operatorStack.pop ();
	}
	else if(!isspace(ch))
		throw
				expressionError("infix2Postfix: Invalid Input");
	if(rank != 1)
		throw
				expressionError("infix2Postfix: Operand expected");
	else
	{
		while(!operatorStack.empty ())
		{
			op=operatorStack.top ();
			operatorStack.pop ();
			if(op.getOp ()=='(')
				throw
				expressionError("infix2Postfix: Missing ')' ");
			else
			{
				postExpression +=op.getOp ();
				postExpression +=' ';
			}
		}
	}
	return postExpression;
}

bool infix2Postfix::isOperator(char ch)const
{
	char opt[6]={'+','-','*','/','^','%'};
	for(int i=0;i<6;i++)
		if(ch=opt[i])
			return true;
		else
			return false;
}