Leetcode-calculatorまとめ

接尾辞式の評価は非常に古典的なテーマであり、主にstackの使用を考察し、本文は主にstackを使用して接尾辞式の評価(±*/カッコを含む)の問題を解決する方法を紹介する.
問題を解く構想.
オペランドとオペレータを格納するために2つのstackを設定し、op_と呼びます.numとop_ch. 次に、遍歴式を示します.

数字に出会ったら、数字全体を取り出してop_num中

スペースに遭遇したらスキップすればいい

オペレータに遭遇した場合は、オペレータopの優先度を見てください.

スタックトップの演算子より優先度が低い場合は、スタックに

を押し込む.

スタックトップの演算子より優先度が等しいか高い場合は、2つのオペランドと1つの演算子を取り出し、演算後に結果をop_に入れるnum(ここでは取り出した演算数がaとbの順であることに注意し、演算時の順序は逆:b演算子a)で、スタックトップ演算子の優先度が演算子opよりも低くなるまで、opをスタックに押し込む.

遍歴後、スタックが空でない場合、演算子とオペランドを絶えず除去し、演算を続け、式が正常に合法である場合、op_ch空いてる時、op_numには1つの結果しか残っていないはずです.それが最終的な式の演算結果です.

TIPS:事前にop_chには「.」などの特殊な演算子が圧入され、優先度を最小限に抑えるように定義し、スタックop_を判断する必要がなくなります.chが空かどうかは,opの優先度とスタックトップの演算子の優先度の関係を判断すればよい.
TIPS:文字列の後ろにスペースを付けておくことをお勧めします.演算には影響しませんが、式からオペランドを取り出すときは、下付き文字が境界を越えているかどうかを判断することは避けられます.(主に以下のような取り出し操作数の方式について)

if (s[i] >= '0' && s[i] <= '9') {
	// number
	int number = 0;
	int p = i;
	while (s[p] >= '0' && s[p] <= '9') {   
	//                ，           ，
 	// c++ stl string        
		number = number * 10 + (s[p] - '0');
		p++;
	}
	i = p - 1;
	op_num.push(number);
	continue;
}

カッコに遭遇したらどうしますか?
左かっこを定義する優先度が最も低いのは、上の3番目のステップでopの優先度とスタックトップの演算子の優先度の関係を比較したときに左かっこの影響を受けないようにするためであり、読み続けることでより深く理解することができます.

左括弧に出会ったら、他のことは言わないで、直接スタックop_に押し込みますchでいい

右括弧に遭遇した場合、操作数と演算子を取り出して計算を行い、左括弧に遭遇するまで左括弧をスタックから取り出し、何もしないで、遍歴を続ければよい.

Basic Calculatorのコードを添付し、Basic CalculatorとBasic Calculator IIについて

int get_priority(char op) {
	switch (op)
	{
	case '+':
	case '-':
		return 1;
	case '*':
	case '/':
		return 2;
	case '(':
	case '.': 
		return 0;
	default:
		return -1;
	}
}

// we need a simple calculator
int calculate(string s) {
	int slength = s.length();
	if (slength == 0)
		return 0;
	s.push_back(' ');
	// normal case
	stack<char> op_ch;
	op_ch.push('.');
	stack<int> op_num;
	int re = 0;
	for (int i = 0; i < slength; i++) {
		//cout << s[i] << endl;
		// start calculate
		if (s[i] == ' ')
			continue;
		if (s[i] >= '0' && s[i] <= '9') {
			// number
			int number = 0;
			int p = i;
			while (s[p] >= '0' && s[p] <= '9') {
				number = number * 10 + (s[p] - '0');
				p++;
			}
			i = p - 1;
			op_num.push(number);
			continue;
		}
		// operator
		if (s[i] == '(') {
			op_ch.push(s[i]);
			continue;
		}
		else if (s[i] == ')') {
			while (op_ch.top() != '(') {
				int b = op_num.top();
				op_num.pop();
				int a = op_num.top();
				op_num.pop();

				switch (op_ch.top()) {
				case '+':
					op_num.push(a + b);
					break;
				case '-':
					op_num.push(a - b);
					break;
				case '*':
					op_num.push(a * b);
					break;
				case '/':
					op_num.push(a / b);
					break;

				}
				op_ch.pop();
			}
			op_ch.pop();
			continue;
		}
		int prior = get_priority(s[i]);
		if (get_priority(op_ch.top()) < prior) {
			op_ch.push(s[i]);
			continue;
		}
		while (get_priority(op_ch.top()) >= prior) {
			int b = op_num.top();
			op_num.pop();
			int a = op_num.top();
			op_num.pop();

			switch(op_ch.top()) {
			case '+':
				op_num.push(a + b);
				break;
			case '-':
				op_num.push(a - b);
				break;
			case '*':
				op_num.push(a * b);
				break;
			case '/':
				op_num.push(a / b);
				break;

			}
			op_ch.pop();
		}
		op_ch.push(s[i]);
	}

	while (op_ch.top() != '.') {
		int b = op_num.top();
		op_num.pop();
		int a = op_num.top();
		op_num.pop();

		switch (op_ch.top()) {
		case '+':
			op_num.push(a + b);
			break;
		case '-':
			op_num.push(a - b);
			break;
		case '*':
			op_num.push(a * b);
			break;
		case '/':
			op_num.push(a / b);
			break;

		}
		op_ch.pop();
	}
	cout << op_num.size() << endl;
	return op_num.top();
}