[演算法心得] ZeroJudge f640.函數運算式求值

jimmyhealer

嗨大家好~ 我是新加入論壇的萌新，之後可能會每日更新一下演算法心得，那目前會在 c/c++ 版，如果大家很熱絡的話再申請 演算法/競賽程式 版吧!

--------------------------------------------------- 正文開始 ---------------------------------------------------

題目名稱: f640: 函數運算式求值
題目網站: ZeroJudge
題目網址: https://zerojudge.tw/ShowProblem?problemid=f640
題目內容:

有三個函數：

f(x) = 2x – 3
g(x, y) = 2x +y – 7
h(x, y, z) = 3x – 2y + z

另有一個由這三個函數所組成的運算式，依序給你其中的函數名稱及參數，請求出這個運算式的值。例如：

h f 5 g 3 4 3

代表

h(f(5), g(3, 4), 3)
=h(7, 3, 3)
=18

範例輸入 #1:
f f f 2
範例輸出 #1:
-5

範例輸入 #2:
h f 5 g 3 4 3
範例輸出 #2:
18

--------------------------------------------------- 題解心得 ---------------------------------------------------

基本上有點像基礎題的四則運算，所以第一個想到的做法就是使用 stack 維護數值。
一開始先把所有運算符跟數字存入陣列之中，接著從後面開始跑。
如果遇到 "數字" 就把他 push 到 stack，遇到 "f" 就將 stack 中的 top 取出來運算完再丟回去 stack。
遇到 "g" 就取兩次，遇到 "h" 就取三次。
最後的答案就是 stack 的 top。

AC code (2ms, 376 KB):

1. #include<bits/stdc++.h>
   
2. #define ll long long
   
3. #define INF 0x3f3f3f3f
   
4. #define MOD 1000000007
   
5. #define io iOS::sync_with_stdio(0);cin.tie(0);cout.tie(0);
   
6. using namespace std;
   
7. const int MXN = 200005;
   
8. 
   
9. //int ar[MXN];
   
10. 
    
11. int f(int x){
    
12.   return 2 * x - 3;
    
13. }
    
14. 
    
15. int g(int x, int y){
    
16.   return 2 * x + y - 7;
    
17. }
    
18. 
    
19. int h(int x, int y, int z){
    
20.   return 3 * x - 2 * y + z;
    
21. }
    
22. 
    
23. int toInt(string s){
    
24.   int cur = 0, op = 1;
    
25.   for(char i : s){
    
26.     if(i == '-'){
    
27.       op = -1;
    
28.       continue;
    
29.     }
    
30.     cur = cur * 10 + i - '0';
    
31.   }
    
32.   return cur * op;
    
33. }
    
34. 
    
35. void sol(){
    
36.   ll ans = 0, n = 0, m = 0, k = 0;
    
37.   
    
38.   string s;
    
39.   vector<string> vec;
    
40.   stack<int> st;
    
41.   while(cin >> s){
    
42.     vec.emplace_back(s);
    
43.   }
    
44. 
    
45.   for(string i : vector<string>(vec.rbegin(), vec.rend())){
    
46.     if(i == "f"){
    
47.       int a = st.top(); st.pop();
    
48.       st.push(f(a));
    
49.     }
    
50.     else if(i == "g"){
    
51.       int a = st.top(); st.pop();
    
52.       int b = st.top(); st.pop();
    
53.       st.push(g(a, b));
    
54.     }
    
55.     else if(i == "h"){
    
56.       int a = st.top(); st.pop();
    
57.       int b = st.top(); st.pop();
    
58.       int c = st.top(); st.pop();
    
59.       st.push(h(a, b, c));
    
60.     }
    
61.     else{
    
62.       st.push(toInt(i));
    
63.     }
    
64.   }
    
65.   cout << st.top() << '\n';
    
66. }
    
67. 
    
68. int main(){
    
69.   //io
    
70.   int t = 1;
    
71.   while(t--){
    
72.     sol();
    
73.   }
    
74. }

複製代碼