Pagini recente » Borderou de evaluare (job #183005) | Borderou de evaluare (job #2109095) | Cod sursa (job #806605) | Cod sursa (job #3245297) | Cod sursa (job #1974122)
#include <iostream>
#include <fstream>
#include <cstring>
#include <stack>
using namespace std;
ifstream in("evaluare.in");
ofstream out("evaluare.out");
const int strMax = 1e5 + 5;
int N,nrPost;
char str[strMax],prio[256];
// str - sirul din input
// prio[c] = precaderea operatorului c ( ( , ) , * , / , + , - )
// (cei cu precadere mai mare se executa primii)
struct elem {
int nr;
char c;
elem(int _nr = 0,int _c = '\0') {
nr = _nr;
c = _c;
}
}postfix[strMax];
// postfix[i] = un element in expresia postfix obtinuta
// care poate fi un numar (retinut in campul nr) sau un operand (retinut in campul c)
int getNumber(int&);
// getNumber return-eaza numarul curent din sirul din input
int main() {
in>>(str+2);
// se adauga paranteze la inceput si sfarsit pentru
// a nu fi nevoie sa se verifice daca stiva este goala
str[1] = '(';
N = strlen(str+1);
str[N += 1] = ')';
prio['('] = prio[')'] = 1;
prio['+'] = prio['-'] = 2;
prio['*'] = prio['/'] = 3;
// se transforma expresia cu notatie infix intr-o expresie
// cu notatie postfix (forma poloneza postfixata)
// folosind shunting-yard algorithm
int i = 1;
stack<char> st;
// st = stiva in care se insereaza operatorii
while (i <= N) {
if ('0' <= str[i] && str[i] <= '9') {
int nr = getNumber(i);
postfix[++nrPost] = elem(nr,'\0');
}
else if (str[i] == '(') {
st.push('(');
}
else if (str[i] == ')') {
while (st.top() != '(') {
postfix[++nrPost] = elem(0,st.top());
st.pop();
}
st.pop();
}
else {
if (prio[str[i]] > prio[st.top()]) {
st.push(str[i]);
}
else {
while (prio[st.top()] >= prio[str[i]]) {
postfix[++nrPost] = elem(0,st.top());
st.pop();
}
st.push(str[i]);
}
}
++i;
}
stack<int> aux;
// se evalueaza expresia postfix obtinuta
// aux = stiva in care se retin operanzii
for (int i=1;i<=nrPost;++i) {
if (postfix[i].c == '\0') {
aux.push(postfix[i].nr);
}
else {
int nr1,nr2,res = 0;
nr1 = aux.top(); aux.pop();
nr2 = aux.top(); aux.pop();
char op = postfix[i].c;
switch (op) {
case '+': {
res = nr2 + nr1;
break;
}
case '-': {
res = nr2 - nr1;
break;
}
case '*': {
res = nr2 * nr1;
break;
}
case '/': {
res = nr2 / nr1;
}
}
aux.push(res);
}
}
out<<aux.top()<<'\n';
in.close();out.close();
return 0;
}
int getNumber(int& i) {
int nr = 0;
while ('0' <= str[i] && str[i] <= '9') {
nr = nr * 10 + (str[i]-'0');
++i;
}
--i;
return nr;
}