Pagini recente » Cod sursa (job #1697646) | Cod sursa (job #2100706) | Cod sursa (job #833222) | Cod sursa (job #3005644) | Cod sursa (job #834270)
Cod sursa(job #834270)
#include <fstream>
#include <iostream>
#include <cstring>
#define MAXN 100000
char operators[] = "+-*/";
char T[MAXN];
char* p;
struct node {
long val;
char op;
node* l;
node* r;
node(int a = 0, char b = 0, node* c = 0, node* d = 0) : val(a),op(b),l(c),r(d){}
int priority()
{
char* c;
if(op && (c = strchr(operators, op)) != NULL)
{
return c-operators;
}
return -1;
}
};
struct stack
{
int size;
int front;
node* nodes[MAXN];
node* pop()
{
if(size==0){
return NULL;
}
node *x = nodes[--size];
nodes[size] = 0;
return x;
}
node* pop_front(){
if(front>size){
return NULL;
}
node *x = nodes[front++];
return x;
}
void push(node* n)
{
if(size<MAXN)
{
nodes[size++] = n;
}
}
int priority()
{
if(size==0){
return -1;
}
return nodes[size-1]->priority();
}
void print() {
for(int i = 0; i<size; i++){
if(nodes[i]->op != 0 ){
std::cout << nodes[i]->op << " ";
} else {
std::cout << nodes[i]->val << " ";
}
}
std::cout << std::endl;
}
long evaluate() {
stack* s = new stack();
node *a, *b, *y;
for(int i = 0; i< size; i++){
node* x = pop_front();
switch(x->op){
case '+':
a = s->pop();
b = s->pop();
y = new node(a->val+b->val);
delete a;
delete b;
s->push(y);
break;
case '-':
b = s->pop();
a = s->pop();
y = new node(a->val - b->val);
delete a;
delete b;
s->push(y);
break;
case '*':
a = s->pop();
b = s->pop();
y = new node(a->val * b->val);
delete a;
delete b;
s->push(y);
break;
case '/':
b = s->pop();
a = s->pop();
y = new node(a->val / b->val);
delete a;
delete b;
s->push(y);
break;
default:
s->push(x);
break;
}
}
node* x = s->pop();
long v = x->val;
delete x;
return v;
}
stack() : size(0), front(0) {}
};
int main(void) {
std::ifstream in("evaluare.in");
std::ofstream out("evaluare.out");
node* x;
stack *rpn = new stack;
stack *ops = new stack;
in.getline(T, MAXN);
p = T;
while(*p != '\0'){
while(*p == ' ') p++;
if(*p >= '0' && *p <= '9'){
x = new node;
while(*p >= '0' && *p <= '9'){
x->val = x->val*10 + *p++ - '0';
}
rpn->push(x);
continue;
}
if(strchr("*/+-", *p))
{
x = new node(0, *p++);
if(ops->priority() != -1 && ops->priority() > x->priority())
{
node* y = ops->pop();
rpn->push(y);
}
ops->push(x);
continue;
}
if(*p == '(')
{
x = new node(0, *p++);
ops->push(x);
continue;
}
if(*p == ')')
{
++p;
x = ops->pop();
while( x->op != '(' )
{
rpn->push(x);
x = ops->pop();
}
continue;
}
}
while(ops->size > 0) {
x = ops->pop();
rpn->push(x);
}
// rpn->print();
long r = rpn->evaluate();
out << r << std::endl;
}