単純計算機逆ポーランド式
3722 ワード
問題C:悠派計算機
時間制限:1 Secメモリ制限:128 MBコミット:7解決:2[コミット][ステータス][ディスカッション版][命題者:qianyouyou]
タイトルの説明
yoyoの弟のくず灰はとても怠け者で、趣味は多くなくて、一人で寝ます.もっと寝坊するために、彼は数学の先生が出した宿題を全部yoyoに計算した.yoyoは頭が痛いので、計算機を書いて計算を手伝ってください.複数の数式があります.計算機の計算結果を書いてください.数式には'+''-'*''/'%'(')'操作のみが含まれています.数式には'-'がマイナス記号として表示されず、'/'は整数演算子であり、'%'は余剰演算子です.式は合法を保証する.
入力
最初の行tを入力して、t行のテスト例を共有し、次にt行の各行が合法的な数学式であることを示します.各数が[09999]の範囲内であることを保証し、計算中に範囲外の状況が発生しないことを保証する.(注:スペースなし)
しゅつりょく
計算結果の出力
サンプル入力
サンプル出力
ヒント
データは水で、long longや取り残しなどを考慮する必要はありません.
問題解
逆ポーランド式は、複雑な式を簡単な操作で計算結果を得ることができる式に変換するのに非常に有用な式です.例えば(a+b)(c+d)をab+cd+に変換する
現在の文字が変数または数値の場合、スタックを圧縮し、演算子の場合、スタックの上部の2つの要素を対応する演算としてポップアップし、結果をスタックに追加します.最後に式のスキャンが完了すると、スタックに結果が表示されます.
例えば(a+b)(c+d)をab+cd+に変換する計算機は、通常の式を計算する際に、演算優先度を再帰的に判断し、より複雑な式に対して計算機の演算効率を低下させ、崩壊させる.逆ポーランド式は、単純なスタックアウトスタック操作を行うだけで、一般式の演算を完了することができます.
一般式-->逆ポーランド式
(1)a+b——>a b +
(2)a+(b-c)——>a b c - +
(3)a+(b-c)d——>a b c - d +
時間制限:1 Secメモリ制限:128 MBコミット:7解決:2[コミット][ステータス][ディスカッション版][命題者:qianyouyou]
タイトルの説明
yoyoの弟のくず灰はとても怠け者で、趣味は多くなくて、一人で寝ます.もっと寝坊するために、彼は数学の先生が出した宿題を全部yoyoに計算した.yoyoは頭が痛いので、計算機を書いて計算を手伝ってください.複数の数式があります.計算機の計算結果を書いてください.数式には'+''-'*''/'%'(')'操作のみが含まれています.数式には'-'がマイナス記号として表示されず、'/'は整数演算子であり、'%'は余剰演算子です.式は合法を保証する.
入力
最初の行tを入力して、t行のテスト例を共有し、次にt行の各行が合法的な数学式であることを示します.各数が[09999]の範囲内であることを保証し、計算中に範囲外の状況が発生しないことを保証する.(注:スペースなし)
しゅつりょく
計算結果の出力
サンプル入力
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
ヒント
データは水で、long longや取り残しなどを考慮する必要はありません.
問題解
逆ポーランド式は、複雑な式を簡単な操作で計算結果を得ることができる式に変換するのに非常に有用な式です.例えば(a+b)(c+d)をab+cd+に変換する
現在の文字が変数または数値の場合、スタックを圧縮し、演算子の場合、スタックの上部の2つの要素を対応する演算としてポップアップし、結果をスタックに追加します.最後に式のスキャンが完了すると、スタックに結果が表示されます.
例えば(a+b)(c+d)をab+cd+に変換する計算機は、通常の式を計算する際に、演算優先度を再帰的に判断し、より複雑な式に対して計算機の演算効率を低下させ、崩壊させる.逆ポーランド式は、単純なスタックアウトスタック操作を行うだけで、一般式の演算を完了することができます.
一般式-->逆ポーランド式
(1)a+b——>a b +
(2)a+(b-c)——>a b c - +
(3)a+(b-c)d——>a b c - d +
#include
using namespace std;
const int maxn = 100007;
mapPri;// map, map
stacknum;
stackOpe;
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;
}
// + )
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){
// , ,
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;
}