[演算法心得] 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):
#include<bits/stdc++.h>
#define ll long long
#define INF 0x3f3f3f3f
#define MOD 1000000007
#define io ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
const int MXN = 200005;
//int ar;
int f(int x){
return 2 * x - 3;
}
int g(int x, int y){
return 2 * x + y - 7;
}
int h(int x, int y, int z){
return 3 * x - 2 * y + z;
}
int toInt(string s){
int cur = 0, op = 1;
for(char i : s){
if(i == '-'){
op = -1;
continue;
}
cur = cur * 10 + i - '0';
}
return cur * op;
}
void sol(){
ll ans = 0, n = 0, m = 0, k = 0;
string s;
vector<string> vec;
stack<int> st;
while(cin >> s){
vec.emplace_back(s);
}
for(string i : vector<string>(vec.rbegin(), vec.rend())){
if(i == "f"){
int a = st.top(); st.pop();
st.push(f(a));
}
else if(i == "g"){
int a = st.top(); st.pop();
int b = st.top(); st.pop();
st.push(g(a, b));
}
else if(i == "h"){
int a = st.top(); st.pop();
int b = st.top(); st.pop();
int c = st.top(); st.pop();
st.push(h(a, b, c));
}
else{
st.push(toInt(i));
}
}
cout << st.top() << '\n';
}
int main(){
//io
int t = 1;
while(t--){
sol();
}
}
頁:
[1]