冰楓論壇

標題: [演算法心得] ZeroJudge f640.函數運算式求值 [打印本頁]
作者: jimmyhealer    時間: 2022-5-8 15:18
標題: [演算法心得] ZeroJudge f640.函數運算式求值
本帖最後由 jimmyhealer 於 2022-5-8 15:20 編輯

嗨大家好~ 我是新加入論壇的萌新，之後可能會每日更新一下演算法心得，那目前會在 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;

  9. //int ar[MXN];

  11. int f(int x){
  12.   return 2 * x - 3;
  13. }

  15. int g(int x, int y){
  16.   return 2 * x + y - 7;
  17. }

  19. int h(int x, int y, int z){
  20.   return 3 * x - 2 * y + z;
  21. }

  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. }

  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.   }

  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. }

  68. int main(){
  69.   //io
  70.   int t = 1;
  71.   while(t--){
  72.     sol();
  73.   }
  74. }
複製代碼




歡迎光臨 冰楓論壇 (https://bingfong.com/) Powered by 冰楓