a017.
五則運算
| From: [61.31.162.92] |
發表日期
:
2009-03-21 22:56
/**********************************************************************************/
/* Problem: a017 "五則運算" */
/* Language: C++ */
/* Result: WA (line:3) on ZeroJudge */
/* Author: asin0622 at 2009-03-21 02:54:32 */
/**********************************************************************************/
#include <iostream>
#include <stack>
#include <queue>
#include <string>
using namespace std;
long double calc( queue<string> q ) {
stack<long double> output;
string op;
long double ele1, ele2, res;
while( !q.empty() ) {
op = q.front(); q.pop();
if ( op[0] >= '0' && op[0] <= '9' ) {
output.push(atoi(op.c_str()));
} else {
switch (op[0]) {
case '+':
ele1 = output.top(); output.pop();
ele2 = output.top(); output.pop();
res = ele1 + ele2;
break;
case '-':
ele1 = output.top(); output.pop();
ele2 = output.top(); output.pop();
res = ele2 - ele1;
break;
case '*':
ele1 = output.top(); output.pop();
ele2 = output.top(); output.pop();
res = ele1 * ele2;
break;
case '/':
ele1 = output.top(); output.pop();
ele2 = output.top(); output.pop();
res = ele2 / ele1;
break;
case '%':
ele1 = output.top(); output.pop();
ele2 = output.top(); output.pop();
res = (long long int)ele2 % (long long int)ele1;
break;
}
output.push(res);
}
}
return output.top();
}
short prio( char op ) {
switch (op) {
case '+':
case '-':
return 1;
case '*':
case '/':
case '%':
return 2;
case '(':
case ')':
return 0;
}
return 0;
}
void rpn( queue<string> &output, stack<string> &oper, const string &s ) {
// RPN -- Reverse Polish notation
if ( s[0] >= '0' && s[0] <= '9' ) {
output.push(s);
} else {
if ( s[0] == ')' ) {
while( !oper.empty() && oper.top()[0] != '(' ) {
output.push(oper.top());
oper.pop();
}
oper.pop();
} else {
if( oper.empty() || s[0] == '(' )
oper.push(s);
else if( prio(s[0]) > prio(oper.top()[0]) )
oper.push(s);
else if( prio(s[0]) <= prio(oper.top()[0]) ) {
output.push(oper.top());
oper.pop(); // pop o2 to queue
oper.push(s); // push o1 to stack
} else {
oper.push(s);
}
}
}
}
int main (int argc, char * const argv[]) {
// insert code here...
string input;
while( getline(cin,input) ) {
if( !input.length() ) continue;
queue<string> output;
stack<string> oper;
// split
int pos = 0;
int len = input.length();
bool isempty = false;
for(int i = 0; i < len; i++ ) {
if ( input[i] == ' ' ) {
if( !isempty ) {
rpn(output, oper, input.substr(pos, i-pos));
}
pos = i + 1;
isempty = true;
}
isempty = false;
}
if( input[pos] != ' ' )
rpn(output,oper,input.substr(pos));
// end split
while( !oper.empty() ) {
output.push(oper.top());
oper.pop();
}
// while ( !output.empty() ) {
// cout << output.front() << " ";
// output.pop();
// }
// return 0;
cout << (long long int)calc(output) << endl;
}
return 0;
}