Pagini recente » Istoria paginii runda/eusebiu_oji_2015_cls10 | Cod sursa (job #1981115) | Cod sursa (job #1562722) | Cod sursa (job #2902596) | Cod sursa (job #1974673)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <cstring>
using namespace std;
ifstream in("evaluare.in");
ofstream out("evaluare.out");
#define pb push_back
#define ll long long
const int strMax = 1e5 + 5;
// se rezolva problema transformand expresia din notatie infix in notatie postfix,
// transformand expresia postfix in arbore de expresie si evaluand arborele
int N;
int prio[1<<8];
// prio[c] = precaderea operatorului c ( ( , ) , * , / , + , - )
// (cei cu precadere mai mare se executa primii)
struct elem {
int nr;
char c;
elem (int _nr = 0,char _c = '\0') {
nr = _nr;
c = _c;
}
};
struct node {
int nr;
char c;
node *st,*dr;
node (int _nr = 0,char _c = '\0',node *_st = nullptr,node *_dr = nullptr) {
nr = _nr;
c = _c;
st = _st;
dr = _dr;
}
node (const node& other) {
nr = other.nr;
c = other.c;
st = other.st;
dr = other.dr;
}
};
// node = un nod in arborele expresiei, reprezentat de un operator sau de un operand (daca este frunza)
int getNumber(char*,int&);
int buildPost(char*,elem*);
node buildTree(elem*,int);
int evaluate(node*);
// getNumber = return-eaza un numar din sirul de input
// buildPost = construieste expresia in forma postfixata din cea infixata, cu algoritmul shunting-yard
// buildTree = construieste arborele din expresia postfix si return-eaza radacina
// evaluate = evalueaza arborele de expresie
int main() {
char *str = new char[strMax];
elem *post = new elem[strMax];
in>>(str+1);
str[0] = '(';
N = strlen(str);
str[N] = ')';
prio['('] = 1;
prio[')'] = 2;
prio['+'] = prio['-'] = 2;
prio['*'] = prio['/'] = 3;
int nrPost = buildPost(str,post);
node root = buildTree(post,nrPost);
out<<evaluate(&root)<<'\n';
in.close();out.close();
return 0;
}
int getNumber(char *str,int& i) {
int ans = 0;
while ('0' <= str[i] && str[i] <= '9') {
ans = ans * 10 + (str[i++]-'0');
}
--i;
return ans;
}
int buildPost(char* str,elem* post) {
int nrPost = 0;
stack<char> stiv;
for (int i=0;i<=N;++i) {
if (str[i] == '(') {
stiv.push('(');
}
else if ('0' <= str[i] && str[i] <= '9') {
int nr = getNumber(str,i);
post[++nrPost] = elem(nr);
}
else {
while (prio[stiv.top()] >= prio[str[i]]) {
post[++nrPost] = elem(0,stiv.top());
stiv.pop();
}
if (str[i] == ')') {
stiv.pop();
}
else {
stiv.push(str[i]);
}
}
}
return nrPost;
}
node buildTree(elem* post,int nrPost) {
stack<node> aux;
for (int i=1;i<=nrPost;++i) {
if (post[i].c == '\0') {
node n(post[i].nr);
aux.push(n);
}
else {
node *n1,*n2,dad;
n1 = new node(aux.top()); aux.pop();
n2 = new node(aux.top()); aux.pop();
dad = node(0,post[i].c,n2,n1);
aux.push(dad);
}
}
return aux.top();
}
int evaluate(node *n) {
switch (n->c) {
case '+': return evaluate(n->st) + evaluate(n->dr);
case '-': return evaluate(n->st) - evaluate(n->dr);
case '*': return evaluate(n->st) * evaluate(n->dr);
case '/': return evaluate(n->st) / evaluate(n->dr);
default: return n->nr;
}
}