問題 C: 悠派計算器

時間限制:?1 Sec??內(nèi)存限制:?128 MB
提交:?7??解決:?2
[提交][狀態(tài)][討論版][命題人:qianyouyou]

題目描述

yoyo的小老弟小渣渣灰特別懶，興趣愛好并不多，就睡覺一個。為了多睡會兒懶覺，他把數(shù)學老師布置的作業(yè)全部推給yoyo計算。yoyo很頭疼，于是請你幫他寫一個計算器幫忙計算。現(xiàn)有多個數(shù)學表達式，請你寫一個計算器算出結果，表達式只包含'+''-''*''/''%''('')'操作，其中表達式中'-'作為減運算符，不會作為負號出現(xiàn)，此外'/'為整除運算符，'%'為取余運算符。表達式保證合法。

輸入

輸入第一行t，表示共有t行測試用例，接下來t行每一行均為一個合法的數(shù)學表達式。保證每個數(shù)在[09999]范圍內(nèi)，保證計算過程中不會出現(xiàn)超范圍情況。（注：沒有空格）

輸出

輸出計算結果

樣例輸入

7 0*1 5%6 1-2*(3+4*5%6)+7/8-9*10%11*12 (1+2*3) 1-(100%5) (3+2*5)/(5) (11-11)+(33)*64-11

樣例輸出

0 5 -135 7 1 2 2101

提示

數(shù)據(jù)很水，不用考慮long long或取余等情況。

題解

逆波蘭表達式是一種十分有用的表達式，它將復雜表達式轉(zhuǎn)換為可以依靠簡單的操作得到計算結果的表達式。例如(a+b)(c+d)轉(zhuǎn)換為ab+cd+

如果當前字符為變量或者為數(shù)字，則壓棧，如果是運算符，則將棧頂兩個元素彈出作相應運算，結果再入棧，最后當表達式掃描完后，棧里的就是結果。

例如(a+b)(c+d)轉(zhuǎn)換為ab+cd+?計算機在計算普通表達式時，要對運算優(yōu)先級用遞歸進行判斷，對于更為復雜的表達式會使計算機運算效率變低甚至崩潰。而逆波蘭表達式只需要進行簡單的入棧出棧操作就可以完成任何普通表達式的運算。

普通表達式——>逆波蘭表達式

(1)a+b——>a b +

(2)a+(b-c)——>a b c - +

(3)a+(b-c)d——>a b c - d?+

#include<bits/stdc++.h> using namespace std; const int maxn = 100007; map<char,int>Pri;//其實可以不必用map，只是為了方便大家理解map而多添加的一步 stack<int>num; stack<char>Ope; char str[maxn]; //初始化 void init(){Pri['+'] = Pri['-'] = 1;Pri['*'] = Pri['/'] = Pri['%'] = Pri['('] = Pri[')'] = 2;while(!num.empty())num.pop();while(!Ope.empty())Ope.pop(); } //基本運算操作 void operation_1(int &a,int &b, char c){if(c == '+')a += b;else if(c == '-')a = b-a;else if(c == '*')a *= b;else if(c == '/')a = b/a;else if(c == '%')a = b%a; } //遇到+或者)時執(zhí)行的操作 void operation_2(){char ch = Ope.top();while(ch != '('&&!Ope.empty()){Ope.pop();int a = num.top();num.pop();int b = num.top();num.pop();operation_1(a,b,ch);num.push(a);if(!Ope.empty())ch = Ope.top();}if(!Ope.empty()&&Ope.top() == '(')Ope.pop(); } int main(){int t;cin>>t;getchar();while(t--){cin.getline(str,maxn);stringstream s(str);init();char tmp;while(s >> tmp){//遇到數(shù)字字符時，需要判斷下一位是否依舊是數(shù)字，是的話需要合并if(tmp >= '0' && tmp <= '9'){int t = 0;do{if(Pri[tmp]){break;}t *= 10;t += tmp - '0';}while(s >> tmp);num.push(t);}//遇到')'時if(tmp == ')'){operation_2();}//遇到'+' ‘-’時else if(Pri[tmp]==1){if(!Ope.empty()&&Ope.top()!='('){operation_2();}Ope.push(tmp);}else if(Pri[tmp]){Ope.push(tmp);}}int ans = num.top();num.pop();while(!num.empty()&&!Ope.empty()){operation_1(ans,num.top(),Ope.top());Ope.pop();num.pop();}cout << ans << endl;}return 0; }

?

總結

以上是生活随笔為你收集整理的简单计算器 逆波兰表达式的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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