zerojudge a017. 五則運算

題目在 https://zerojudge.tw/ShowProblem?problemid=a017

我用兩個堆疊, 一個nums放數字, 一個ops放運算子, 當要計算時, 就從堆疊裡拿兩個數字和一個運算子來計算.算完的結果再丟進推疊裡.

stack<int> nums;
stack<char> ops;

void do_calculate() {
	int num2 = nums.top();
	nums.pop();
	int num1 = nums.top();
	nums.pop();
	char op = ops.top();
	ops.pop();
	int result;
	switch (op) {
		case '+': result = num1 + num2; break;
		case '-': result = num1 - num2; break;
		case '*': result = num1 * num2; break;
		case '/': result = num1 / num2; break;
		case '%': result = num1 % num2; break;
		default: break;
	}
	nums.push(result);
}

C++

什麼時候要計算?什麼時候要丟進堆疊? 根據的是運算的優先次序.

先把運算的順序分成兩類: 加減比較低, 乘除和餘數運算比較高.

int get_priority(char op) {
	if (op == '+' || op == '-') return 1;
	if (op == '*' || op == '/' || op == '%') return 2;
	return -1;
}

C++

如果剖析字串時遇到的運算次序沒有比堆疊裡的高, 堆疊裡的計算就可以先算了. 算完後, 這次的運算先丟進堆疊,因為還不知道右邊的數字.

if (c == '+' || c == '-' || c == '*' || c == '/' || c == '%') {
	while (!ops.empty() && get_priority(ops.top()) >= get_priority(c)) {
		do_calculate();
	}
	ops.push(c);
}

C++

至於遇到左括號就用遞迴從下一個字元開始計算括號內的數字, 這樣遇到右括號時就開始計算直到回到上個左括號. 注意return時要回傳i, 上層才知道算到哪裡了.

                if (c == '('){
			ops.push(c);
			i++;
			i = parser(i, length);
		} else if (c == ')'){
			while('(' != ops.top()){
				do_calculate();
			}
			ops.pop();
			return i;
		}

C++

最後當整個運算式都剖析完, 堆疊裡還沒有算完的話, 全部pop出來計算到空為止.

while (!ops.empty()) {
	do_calculate();
}

C++

下面是用debug message來感覺一下計算2 * ( 3 + 4 ) * 5過程.

2 * ( 3 + 4 ) * 5
push 2
push *
push (
push 3
push +
push 4
meet )
3 + 4 = 7
ops.pop
return i=12
2 * 7 = 14
push *
push 5
14 * 5 = 70
70

C++

完整程式如下,debug message我沒拿掉.

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

using namespace std;

stack<int> nums;
stack<char> ops;
string str;


int get_priority(char op) {
	if (op == '+' || op == '-') return 1;
	if (op == '*' || op == '/' || op == '%') return 2;
	return -1;
}

void do_calculate() {
	int num2 = nums.top();
	nums.pop();
	int num1 = nums.top();
	nums.pop();
	char op = ops.top();
	ops.pop();
	int result;
	switch (op) {
		case '+': result = num1 + num2; break;
		case '-': result = num1 - num2; break;
		case '*': result = num1 * num2; break;
		case '/': result = num1 / num2; break;
		case '%': result = num1 % num2; break;
		default: break;
	}
	printf("%d %c %d = %d\n", num1, op, num2, result);
	nums.push(result);
}

int parser(int index, int length){
	for (int i = index; i < length; i++) {
		char c = str[i];
		if (isdigit(c)) {
			int num = 0;
			while (i < length && isdigit(str[i])) {
				num = num * 10 + str[i] - '0';
				i++;
			}
			i--;
			nums.push(num);
			printf("push %d\n",num);
		} else if (c == '+' || c == '-' || c == '*' || c == '/' || c == '%') {
			while (!ops.empty() && get_priority(ops.top()) >= get_priority(c)) {
				do_calculate();
			}
			ops.push(c);
			printf("push %c\n",c);

		} else if (c == '('){
			printf("push %c\n",c);
			ops.push(c);
			i++;
			i = parser(i, length);
			printf("return i=%d\n",i);
		} else if (c == ')'){
			printf("meet %c\n",c);
			char op;
			while('(' != ops.top()){
				do_calculate();
			}
			ops.pop();
			printf("ops.pop\n");
			return i;
		} else if (c == ' '){
		}
	}
	while (!ops.empty()) {
		do_calculate();
	}
}

int main() {
	while (getline(cin, str)) {
		int len = str.size();
		parser(0, len);
		cout << nums.top() << endl;
		nums = stack<int>();
		ops = stack<char>();
	}
	return 0;
}

C++

zerojudge a017. 五則運算

Archives

Categories