2012-12-08 14:09:26Morris
[ZJ][三年後修正版] a017. 五則運算
內容 ：
計算五則運算式的結果，包含加、減、乘、除、餘
輸入說明
：
輸入一個字串，其中包含運算元及運算子，為了方便讀取，所有的運算子及運算元均以空格區隔。
運算元為 0 ~231 -1 的整數
運算子則包含 + - * / % 及 ( )
運算時請注意先乘除後加減及() 優先運算的計算規則
輸出說明
：
輸出結果。為了避免小數點誤差，所有的運算過程都不會產生小數點，可以放心使用整數進行運算
範例輸入 ：
2 + 3 * 4 2 * ( 3 + 4 ) * 5
範例輸出 ：
14 70
提示
：
* 可使用 stringstream 及 getline 來讀取及分析字串
出處
：
/********************************************/
/* Problem: a017 "五則運算" */
/* Language: CPP (4335 Bytes) */
/* Result: AC(4ms, 460KB) judge by this@ZeroJudge */
/* Author: morris1028 at 2012-12-07 16:17:56 */
/********************************************/
#include <iostream>
#include <sstream> // stringstream
#include <ctype.h> // isdigit()
using namespace std;
//<stack template>
template <typename T>
struct Node {
T d;
Node *prev;
};
template <class T>
class STACK { // linked list implements stack
public:
STACK() {
idx = NULL;
SIZE = 0;
}
T top() {
T cpy = idx->d;
return cpy;
}
void pop() {
Node<T> *tmp;
tmp = idx;
idx = idx->prev;
delete tmp;
SIZE--;
}
void push(T item) {
Node<T> *nd = new Node<T>;
nd->d = item;
nd->prev = idx;
idx = nd;
SIZE++;
}
bool empty() {
return idx == NULL;
}
int size() {
return SIZE;
}
private:
Node<T> *idx;
int SIZE;
};
//</stack template>
//<parse infix>
int priority(char c) {
switch(c) {
case '(':return 1;
case '+':return 2;
case '-':return 2;
case '*':return 3;
case '/':return 3;
case '%':return 3;// please ignore mod
}
return -1; // error state
}
string infix2postfix(string infix) {
string postfix = "";
int i, j, len = infix.length();
STACK<char> opStk; // save operator, not number
for(i = 0; i < len; i++) {
if(infix[i] == ' ')
continue;
if(isdigit(infix[i])) { // cut number
while(i < len && isdigit(infix[i])) {
postfix += infix[i];
i++;
}
i--; // because for loop i++
postfix += ' ';
} else { // operator or '(' or ')'
if(infix[i] == ')') {
while(opStk.top() != '(') {
postfix += opStk.top();
postfix += ' ';
opStk.pop();
}
opStk.pop(); // pop '('
} else {
while(!opStk.empty() && infix[i] != '(') {
if(opStk.top() != '(') {
if(priority(opStk.top()) >= priority(infix[i])) {
postfix += opStk.top();
postfix += ' ';
opStk.pop();
} else
break;
} else
break;
}
opStk.push(infix[i]);
}
}
}
while(!opStk.empty()) {
postfix += opStk.top();
postfix += ' ';
opStk.pop();
}
return postfix;
}
//</parse infix>
//<calc postfix>
int calcPostfix(string postfix) {
STACK<int> stk;
stringstream sin(postfix), str2int;
string token;
int a, b, neg;
while(sin >> token) {
switch(token[0]) {
case '+': case '-': case '*': case '/': case '%':
b = stk.top(), stk.pop();
a = stk.top(), stk.pop();
neg = 1; // exist neg number
if(token == "+")
stk.push(a+b), neg = 0;
if(token == "-")
stk.push(a-b), neg = 0;
if(token == "*")
stk.push(a*b), neg = 0;
if(token == "/")
stk.push(a/b), neg = 0;
if(token == "%")
stk.push(a%b), neg = 0;
if(neg == 0)
break;
default:
str2int.clear();
str2int << token;
str2int >> a;
stk.push(a);
}
}
if(stk.size() != 1)
cout << "Error" << endl;
return stk.top();
}
//</calc postfix>
int main() {
string infix, postfix;
while(/*cout << "Please enter an infix expression: ",*/
getline(cin, infix)) {// EOF window ctrl+z+enter, linux ctrl+d
postfix = infix2postfix(infix);
/*cout << "postfix expression: " << postfix << endl;
cout << "calculate result: " << calcPostfix(postfix) << endl;*/
cout << calcPostfix(postfix) << endl;
}
return 0;
}