C++式の評価(ツリーとスタックでそれぞれ説明)

例えば「(123-5)*6+(9-8)*(5-6)-(10-2*(3-9)」のような式の値を求める.
このような問題には2つの方法があり,1つ目は二叉木の性質を利用して表現木スタックを構築することである.第2の方法は,2つのスタック,1つの演算子,1つのデータを用いて,優先順位順で演算操作を行う.
1)ツリーによる記述
まず式ツリースタックを構築し,式全体を優先度に従って各サブ式に分解し,サブ式をツリーのノードに割り当てて表現ツリースタックを構成する.表現ツリースタックが作成されると、ルートノードから式の値を再帰的に計算できます.表現ツリースタックの作成手順は次のとおりです.
  

struct expression
{//   
	char op;
	expression* left;
	expression* right;
	double value;
	expression(char theOp):op(theOp),left(nullptr),right(nullptr){  }
	expression(double theValue) :value(theValue), op('#') {
		left = right = nullptr;
	}
};
class expTree
{//    
public:
	expTree(const string& str)
	{//   
		int n = str.size() - 1;
		GenExpTree(str, 0,n, root);
	}
	~expTree() { postOrderErase(root); } //   
	void postOrderErase(expression* &exp)
	{//    
		if (exp != nullptr) {
			postOrderErase(exp->left);
			postOrderErase(exp->right);
			delete exp;
		}
	}
	double calculate() { return myCal(root); }
	double myCal(expression* &exp)
	{
		if (exp != nullptr) {
			if (exp->op == '#') {
				return exp->value;
			}
			double x = myCal(exp->left);
			double y = myCal(exp->right);
			switch (exp->op)
			{
			case'+':return x + y;
			case'-':return x -y;
			case'*':return x*y;
			case'/':return x / y;
			}
		}
	}
private:
	expression* root;
	void GenExpTree(const string& str, int b, int e, expression* & exp)
	{
		if (b e) {
			exp = nullptr;
			return;
		}
		int brackets = 0;
		int lastPS = -1, lastMD = -1;
		bool findChar=false;
		for (int i = b; i <=e; i++)
		{
			if (str[i] != '.'&&str[i]'9') {//   
				findChar = true;
				switch(str[i])
				{
				  case'(': brackets++; break;
				  case')': brackets--; break;
         
				  case'+': 
				  case'-': if(!brackets)lastPS=i; break;

				  case'*':
				  case'/': if (!brackets)lastMD=i; break;
				}
			}
		}
		if (!findChar) {
			exp = new expression(stod(str.substr(b, e - b + 1)));
			return;
		}
		if (lastPS == -1) {
			lastPS = lastMD;
		}
		exp = new expression(str[lastPS]);
		GenExpTree(str, b, lastPS - 1, exp->left);
		GenExpTree(str, lastPS+1,e, exp->right);
	}
};
void testExpression()
{
    string str = "(123-5)*6+(9-8)*(5-6)-(10-2*(3+8))+8*(9-1)";
	expTree expT(str);
	cout << expT.calculate() << endl;   //  783

}

2)2つのスタックで説明する
1つのスタックは演算子を配置するために使用され、もう1つのスタックはデータを配置するために使用されます.基本的な考え方は、演算子スタックが空の場合、演算子スタックに直接追加します.そうしないと、スタック外とスタック内の演算子の優先度を比較し、スタック内の演算子の優先度が高い場合(スタック内の演算子とスタック外の演算子が1つの優先度にあり、スタック内の優先度が高いと考えられます)スタック内の演算子をポップアップします.さらに2つのデータをポップアップして演算し、結果を再びデータスタックに押し込みます.もちろん、新しく来た演算子も演算子スタックに入れます.スタック外の演算子が高い場合は、演算子スタックに直接演算子を押し込みます.')'に出会った場合は、カッコのペアがあることを示します.この場合はカッコの値を計算し、結果をデータスタックに押し込みます.もちろん')'はスタックには入りません.そして前の「(’削除.最後に遍歴中に出会ったのがデータ文字であれば、直接長さを検索し、持続的なデータを先にデータ変換stodを行い、結果をデータスタックに押し込む.遍歴完了後、優先度の関係で、まだ計算されていないデータもあるかもしれないが、この場合の演算優先度はスタックの出スタック順に完全に従っているので、演算子まで直接出スタックして計算するスタックは空で、このときのデータスタックにも1つの要素しか残っていないのが最後の計算結果であり、この唯一のスタックトップ要素を返します.
         

int priority(char a, char b)
{//a        ，b        
	if (b == '+' || b == '-' )
	{
		if (a == '+' || a == '-' || a == '*' || a == '/') {//       
			return 1;
		}
		else if (a == '(') {//       
			return -1;
		}
	}
	else if (b == '*' || b == '/') {
		if (a == '*' || a == '/') {//       
			return 1;
		}
		else if (a == '+' || a == '-' || a == '(') {//       
			return -1;
		}
	}
	else if (b == '(') {//       
		return -1;
	}
	return 0;
}
double calculate(double x, char op, double y)
{
	switch (op)
	{
	    case '+':return x + y;
		case '-':return x - y;
		case '*':return x * y;
		case '/':return x / y;
	}
}
double expStack(const string& str)
{
	stack opor;
	stackopnd;
	int i = 0;
	while (i < str.size()) {
		if (str[i] != '.'&&str[i]'9') {
			if (opor.empty() || priority(opor.top(), str[i]) < 0) {//      
				opor.push(str[i]);
			}
			else if (priority(opor.top(),str[i]) > 0) {//      
				double a = opnd.top();
				opnd.pop();
				double b = opnd.top();
				opnd.pop();
				opnd.push(calculate(b, opor.top(), a));

				opor.pop();
				opor.push(str[i]);
			}
			else if (str[i] == ')') {//       
				while (opor.top() != '(') {
					double a = opnd.top();
					opnd.pop();
					double b = opnd.top();
					opnd.pop();
					opnd.push(calculate(b, opor.top(), a));

					opor.pop();
				}
				opor.pop();
			}
			++i;
		}
		else {//  
			int k = i;
			while (str[i] == '.' || str[i] >= '0'&&str[i] <='9') {
				i++;
			}
			opnd.push(stod(str.substr(k, i - k)));
		}
	}
	//      
	while (!opor.empty()) {
		double a = opnd.top();
		opnd.pop();
		double b = opnd.top();
		opnd.pop();
		opnd.push(calculate(b, opor.top(),a));

		opor.pop();
	}
	return opnd.top();
}
void testExpression()
{
	string str = "(123-5)*6+(9-8)*(5-6)-(10-2*(3+8))+8*(9-1)";
	//string str = "(9-7)*(5-6)";
	//string str = "4+3*(5+2/1)";
	cout << expStack(str) << endl;  //  783
}