填寫問券˙抽7-11禮券直擊★美車模手癢不小心...攝影界美人正妹指定相機款反服貿流血 法官要警交...
2013-02-19 21:58:57 人氣(83) | 回應(0) | 推薦(0) | 收藏(0) 上一篇 | 下一篇

[UVA][五則運算] 622 - Grammar Evaluation

0
收藏
0
推薦


  Grammar Evaluation 

Using the following grammar:

<expression> := <component> | <component> + <expression>
<component> := <factor> | <factor> + <component>
<factor> := <positive integer> | (<expression>)

write a program which analyses expressions conforming to the rules of this grammar and evaluates them, if the analysis has been successfully completed. It may be assumed that there is no overflow of float(C)/real(Pascal) numbers range.

Input 

A integer n stating the number of expressions, then consecutive n lines, each containingan expression given as a character string.

Output 

For each line value of the expression or output message ERROR if the expression does not follow the grammar.

Sample Input 

5
32
12+34
1*(2+3)+3
1(2+3)+3
qwe323

Sample Output 

32
46
8
ERROR
ERROR

五則運算檢查不合法的 stack 操作,但這裡的除了 +* 以外的運算都是錯誤的。


#include <iostream>
#include <sstream> // stringstream
#include <ctype.h> // isdigit()
#include <stdio.h>
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>
int error;
//<parse infix>
int priority(char c) {
switch(c) {
case '(':return 1;
case '+':return 2;
case '-':return 2;
case '*':return 3;
}
error = 1;
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.size() && opStk.top() != '(') {
postfix += opStk.top();
postfix += ' ';
opStk.pop();
}
if(opStk.size())
opStk.pop(); // pop '('
else error = 1;
} 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>
void calcPostfix(string postfix) {
STACK<int> stk;
stringstream sin(postfix), str2int;
string token;
int a, b;
while(sin >> token) {
switch(token[0]) {
case '+': case '*':
if(stk.size() == 0) {error = 1;return;}
b = stk.top(), stk.pop();
if(stk.size() == 0) {error = 1;return;}
a = stk.top(), stk.pop();
if(token == "+")
stk.push(a+b);
else if(token == "*")
stk.push(a*b);
else
{error = 1;return;}
break;
default:
str2int.clear();
str2int << token;
if(str2int >> a) {}
else {error = 1;return;}
stk.push(a);
}
}
if(stk.size() != 1) {error = 1;return;}
printf("%d\n", stk.top());
}
//</calc postfix>
int main() {
string infix, postfix;
getline(cin, infix);
while(getline(cin, infix)) {
error = 0;
postfix = infix2postfix(infix);
//cout << postfix << endl;
if(!error)
calcPostfix(postfix);
if(error)
puts("ERROR");
}
return 0;
}

622Grammar Evaluation
台長:Morris
人氣(83) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 不分類 | 個人分類: UVA |
此分類下一篇:[UVA][bfs] 12101 - Prime Path
此分類上一篇:[UVA][計數] 10625 - GNU = GNU'sNotUnix

我要回應
是 (若未登入"個人新聞台帳號"則看不到回覆唷!)
* 請輸入識別碼:
請輸入以下數字 (ex:123)

(有*為必填)
詳全文