【題目鏈接】

OpenJudge NOI 3.3 3340:RPN Calculator

【題目翻譯】

逆波蘭表示法計算器

描述

逆波蘭表示法與波蘭表示法類似。波蘭表示法是由波蘭數(shù)學家揚·武卡謝維奇于1920年引入的，是一種每個操作符都在它的操作數(shù)后面的數(shù)學表示法，它也被稱作：前綴表示法。
在逆波蘭表示法中運算符在它們的操作數(shù)后面；例如，要表示三加四，一個人應該寫“3 4 +”，而不是“3 + 4”。如果有多個運算符，運算符必須直接出現(xiàn)在它的第二個操作數(shù)后面。所以，用傳統(tǒng)的中綴表示法寫出的“3 - 4 + 5”在逆波蘭表示法中寫為“3 4 - 5 +”：先做3減4，再加5。逆波蘭表示法的好處是它避免了在一些中綴表示法中必須寫的括號。“3 - 4 * 5”也可以寫為“3 - (4 * 5)”，它與“(3 - 4) * 5”的意義非常不同，只有使用括號才能區(qū)分二者的意義。在前綴表示法中，前面的一個表達式可以寫為：“3 4 5 * -”，這也能無歧義第表示“3 (4 5 *)”
要求你設計一個簡單的逆波蘭表達式計算器，需要支持$+,?,?,/$，（除數(shù)的絕對值不小于$10^{?9}$）與^（乘方運算符，如果底數(shù)$b\le 0$，那么指數(shù)$e$一定是一個正數(shù)而且不大于$10^9$。
你可以認為運算中涉及到的所有的數(shù)字都可以由雙精度浮點型變量表示。
另外，我們的計算器有一些“內(nèi)存”。每次我們計算一個表達式，“內(nèi)存”中最小的數(shù)字會被當前表達式的值替換掉。

輸入：

第一行包含一個整數(shù)n，表示計算器的“內(nèi)存”大小。
從第二行開始，我們會給出n個數(shù)字，為“內(nèi)存”中的初始值。除了最后一行，每行會給出10個數(shù)字。
然后每行有一個合法的我們之前描述的逆波蘭表達式，以“=”結(jié)束。“=”是計算的指令。每項不會超過20個字符。

輸出：

對于每個表達式，在一行內(nèi)輸出它的值。
然后輸出一個空行分隔兩部分。
最后，以升序輸出內(nèi)存中的所有的數(shù)字，10個數(shù)字一行。
每個數(shù)字必須以科學計數(shù)法表示，整數(shù)小數(shù)點后保留6位，指數(shù)保留2位。（就像C語言中用printf("%e")格式化字符串一樣）一行中的各個數(shù)字應該用空格分隔。

樣例輸入

4
1e6 1e-6 0.001 1000
1 2 + 3 4 + * =
1 0.1 / 8 ^ =

樣例輸出

2.100000e+01
1.000000e+08

2.100000e+01 1.000000e+03 1.000000e+06 1.000000e+08

提示

有大量輸入，建議使用scanf()
%e格式輸出在windows環(huán)境下指數(shù)部分為3位，在系統(tǒng)的測試環(huán)境下為2位。

【題目考點】

1. 表達式求值

2. 表達式樹

表達式樹：一棵表達式樹可以表示一系列的運算。
表達式樹中的結(jié)點包括運算符與數(shù)值

struct Node {char c;//運算符int n;//數(shù)值 }

• 分支結(jié)點：c:運算符，n:該子樹對應的表達式的值
• 葉子結(jié)點：c:'\0'，n:數(shù)值
  表達式樹的值，是左子樹的值和右子樹的值，經(jīng)過根結(jié)點運算符運算后得到的結(jié)果。

【解題思路】

解法1：后綴表達式直接求值

從左向右掃描后綴表達式。

遇到數(shù)字時，將數(shù)字入棧。

遇到運算符時，彈出棧頂?shù)膬蓚€數(shù)，用該運算符對它們做相應的計算，結(jié)果入棧。

掃描結(jié)束后，棧頂數(shù)字就是結(jié)果。

解法2：后綴表達式構(gòu)造表達式樹

如果讀到數(shù)字，那么新建數(shù)字結(jié)點入棧。

如果讀到運算符，則新建運算符結(jié)點np，出棧兩個結(jié)點，將這兩個結(jié)點的值通過np的運算符運算后得到的值存為新結(jié)點np的值，將np入棧。

讀完整個后綴表達式，棧中應該只剩1個結(jié)點，該結(jié)點就是表達式樹的根結(jié)點，該結(jié)點的值就是表達式的值 。

解法3：遞歸

先將字符串處理為由結(jié)構(gòu)體對象構(gòu)成的后綴表達式，每個結(jié)構(gòu)體對象可能是數(shù)字可能是運算符。
后綴表達式的結(jié)構(gòu)為：<第一個運算單元><第二個運算單元><運算符>
每個運算單元也許是一個數(shù)字，也許是一個后綴表達式。
后綴表達式數(shù)組最后一個元素的下標為p。
設函數(shù)solve()，求從第p位置開始向左遍歷取到的第一個運算單元的值。每取一個元素，p向左移動一個位置。

• 如果p位置是數(shù)字，直接返回這個數(shù)字的值。
• 如果p位置是運算符，那么從p位置開始向左取兩個運算單元的值，并用當前位置的運算符進行計算，得到這一運算單元的值。

【題解代碼】

解法1：后綴表達式直接求值

#include <bits/stdc++.h> using namespace std; #define N 105 struct Node {double n;char c; }; Node eq[N]; int p; priority_queue<double, vector<double>, greater<double> > pq;//小頂堆 double calc(double a, double b, char c) {switch(c){case '+':return a+b;case '-':return a-b;case '*':return a*b;case '/':return a/b;case '^':return pow(a, b);} } double solve()//求解后綴表達式eq {stack<double> stk;for(int i = 1; i <= p; ++i){if(eq[i].c == '\0')stk.push(eq[i].n);else{double b = stk.top();stk.pop();double a = stk.top();stk.pop();stk.push(calc(a, b, eq[i].c));}}return stk.top(); } int main() {char s[25];double a, ans; int n, ct = 0;//ct:輸出個數(shù) scanf("%d", &n);for(int i = 1; i <= n; ++i){scanf("%lf", &a);pq.push(a);}while(scanf("%s", s) != EOF){if(s[0] >= '0' && s[0] <= '9' || s[0] == '-' && s[1] >= '0' && s[1] <= '9')//如果s是數(shù)字（可能是負數(shù)） {eq[++p].n = atof(s);//將字符串s轉(zhuǎn)為浮點數(shù)。eq[p].c = '\0'; }else if(strcmp(s, "=") == 0)//遇到等號，求解后綴表達式 {ans = solve();printf("%e\n", ans);pq.pop(); pq.push(ans);//將求解的結(jié)果存入堆 p = 0;}else//是+-*/^ {eq[++p].n = 0;eq[p].c = s[0];}}putchar('\n');while(pq.empty() == false){ printf("%e ", pq.top());ct++;if(ct == 10){putchar('\n');ct = 0;}pq.pop();}return 0; }

解法2：遞歸

#include <bits/stdc++.h> using namespace std; #define N 105 struct Node {double n;char c; }; Node eq[N]; int p; priority_queue<double, vector<double>, greater<double> > pq;//小頂堆 double calc(double a, double b, char c) {switch(c){case '+':return a+b;case '-':return a-b;case '*':return a*b;case '/':return a/b;case '^':return pow(a, b);} } double solve()//求解后綴表達式eq {int lp = p--;if(eq[lp].c == '\0')//如果是數(shù)字 return eq[lp].n;else{double b = solve();double a = solve();return calc(a, b, eq[lp].c);} } int main() {char s[25];double a, ans; int n, ct = 0;//ct:輸出個數(shù) scanf("%d", &n);for(int i = 1; i <= n; ++i){scanf("%lf", &a);pq.push(a);}while(scanf("%s", s) != EOF){if(s[0] >= '0' && s[0] <= '9' || s[0] == '-' && s[1] >= '0' && s[1] <= '9')//如果s是數(shù)字（可能是負數(shù)） {eq[++p].n = atof(s);//將字符串s轉(zhuǎn)為浮點數(shù)。eq[p].c = '\0'; }else if(strcmp(s, "=") == 0)//遇到等號，求解后綴表達式 {ans = solve();printf("%e\n", ans);pq.pop(); pq.push(ans);//將求解的結(jié)果存入堆 p = 0;}else//是+-*/^ {eq[++p].n = 0;eq[p].c = s[0];}}putchar('\n');while(pq.empty() == false){ printf("%e ", pq.top());ct++;if(ct == 10){putchar('\n');ct = 0;}pq.pop();}return 0; }

總結(jié)

以上是生活随笔為你收集整理的OpenJudge NOI 3.3 3340:RPN Calculator的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。