Koios1143的筆記

Zerojudge a017

發表於 更新於 分類於

Zerojudge a017

題敘

https://zerojudge.tw/ShowProblem?problemid=a017
給定一個中序運算式，包含 + - * / % ，求運算結果

想法

對於中序運算在想法上比較不容易思考，改成後序運算會更佳
因此我先將給定運算式轉成後序運算式，再進行運算

簡單介紹一下前、中、後序運算
例如在中序運算式是 1 + ( 2 + 3 * 5 ) % 2

前序

前序運算會將上述的運算式改成 + 1 % + 2 * 3 5 2
從右邊看回來

  1. + 1 % + 2 15 2
  2. + 1 % 17 2
  3. + 1 1
  4. 2

中序

中序運算是由左向右看，遇到括號從內往外看，先乘除後加減
平常我們使用的都是中序運算

  1. 1 + ( 2 + 15 ) % 2
  2. 1 + ( 17 ) % 2
  3. 1 + 1
  4. 2

後序

後序運算會先將上述運算式改成 1 2 3 5 * + 2 % +
從左邊看過去，遇到運算子就向前取兩個運算元進行計算

  1. 1 2 15 + 2 % +
  2. 1 17 2 % +
  3. 1 1 +
  4. 2

(也可參考此資料: https://magiclen.org/arithmetic/)

後序運算會先將運算元放入，再將運算子放入
這邊會用一個stack儲存運算元，並用vector或queue儲存結果
為了達到先乘除後加減，需要對運算子的優先度進行判斷
轉換情況如下

  1. 遇到運算元，直接放入結果
  2. 遇到 (，直接放入stack
  3. 遇到運算子
    1. 將stack頂端所有優先度<=當前運算子的都放入結果
    2. 將當前運算子放入stack
  4. 遇到)，將stack中所有在(後的元素都放入結果，並將(移除

而這裡轉換成後序運算式後我們可以利用stack達成計算
從左邊開始，每次將運算內容放進stack
遇到運算子就從stack拿出兩個運算元計算，再重新推入stack
重複直到運算式結束

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
//By Koios1143
#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
using namespace std;
stack<string> op;
string input,tr;
queue<string> res;
int prior(string ch){
	if(ch=="+" || ch=="-") return 1;
	else if(ch=="*" || ch=="/" || ch=="%") return 2;
	else return 0;
}

bool is_op(string ch){
	if(ch=="+" || ch=="-" || ch=="*" || ch=="/" || ch=="%")
		return true;
	return false;
}

void to_post(string s){
	stringstream ss;
	ss<<input;
	while(!res.empty()) res.pop();
	while(ss>>tr){
		if(is_op(tr)){
			while(!op.empty() && prior(tr) <= prior(op.top())){
				res.push(op.top());
				op.pop();
			}
			op.push(tr);
		}
		else if(tr == "("){
			op.push(tr);
		}
		else if(tr == ")"){
			while(op.top()!="("){
				res.push(op.top());
				op.pop();
			}
			op.pop();
		}
		else{
			res.push(tr);
		}
	}
	while(!op.empty()){
		res.push(op.top());
		op.pop();
	}
}

int string_to_num(string s){
	int ret = 0;
	for(int i=0 ; i<s.size() ; i++){
		ret*=10;
		ret+=s[i]-'0';
	}
	return ret;
}

int main(){
	while(getline(cin,input)){
		to_post(input);
		stack<int> nums;
		while(!res.empty()){
			if(is_op(res.front())){
				int b = nums.top();
				nums.pop();
				int a = nums.top();
				nums.pop();
				
				if(res.front() == "+"){
					nums.push(a+b);
				}
				else if(res.front() == "-"){
					nums.push(a-b);
				}
				else if(res.front() == "*"){
					nums.push(a*b);
				}
				else if(res.front() == "/"){
					nums.push(a/b);
				}
				else{
					nums.push(a%b);
				}
				res.pop();
			}
			else{
				nums.push(string_to_num(res.front()));
				res.pop();
			}
		}
		cout<<nums.top()<<'\n';
		nums.pop();
	}
	return 0;
}

複雜度

轉成後序運算式的複雜度為 $O(len(input))$

計算的時間複雜度也約為 $O(len(input))$

整體複雜度為 $O(2len(input))$ ，約為 $O(len(input))$