Pagini recente » Cod sursa (job #3039218) | Cod sursa (job #1709298) | Cod sursa (job #469791) | Cod sursa (job #366718) | Cod sursa (job #965169)
Cod sursa(job #965169)
#include <fstream>
#include <string.h>
#include <stack>
#define NMax 100000
#define LGElem 10000
using namespace std;
ifstream fin("evaluare.in");
ofstream fout("evaluare.out");
char sir[NMax];
// converteste o expresie aritm. din infix in postfix
char* convToPostFix(char *sir);
// compara doi operatori aritmetici
int compOperatori(char x, char y);
// rezolva o expresie aritmetica in postfix
int rezolvaExp(char *sir);
int main()
{
fin >> sir;
fout << rezolvaExp(convToPostFix(sir));
return 0;
}
// rezolva o expresie aritmetica in postfix
int rezolvaExp(char *sir)
{
int i, aux, aux2, lgElem = 0, lg = strlen(sir);
char elem[LGElem];
stack<int> rez;
elem[0] = NULL;
for (i=0; i<lg; i++)
{
// nr pe poz curenta
if ('0' <= sir[i] && sir[i] <= '9')
{
elem[lgElem++] = sir[i];
elem[lgElem] = NULL;
}
else
{
// daca exista un element citit, il punem in stiva
if (lgElem > 0)
{
aux = atoi(elem);
rez.push(aux);
lgElem = 0;
}
if (sir[i] == '+' || sir[i] == '-' || sir[i] == '*' || sir[i] == '/' && rez.size() >= 2)
{
aux = rez.top(), rez.pop();
aux2 = rez.top(), rez.pop();
switch (sir[i])
{
case '+': rez.push(aux+aux2); break;
case '-': rez.push(aux2-aux); break;
case '*': rez.push(aux*aux2); break;
case '/': rez.push(aux2/aux); break;
}
}
}
}
return rez.top();
}
char* convToPostFix(char *sir)
{
int i, lgElem = 0, lgRez = 0, lg = strlen(sir);
char elem[LGElem], rez[NMax], c;
stack<char> op;
elem[0] = NULL;
rez[0] = NULL;
for (i=0; i<lg; i++)
{
// nr pe poz curenta
if ('0' <= sir[i] && sir[i] <= '9')
{
elem[lgElem++] = sir[i];
elem[lgElem] = NULL;
}
else
{
// daca exista un element citit, il punem in sirul final
if (lgElem > 0)
{
if (lgRez > 0)
{
strcat(rez, " ");
lgRez++;
}
strcat(rez, elem);
lgRez += lgElem;
// nu mai avem nici un element acum
lgElem = 0;
}
if (op.empty())
{
op.push(sir[i]);
}
else
{
// stiva nu este goala in acest moment
c = op.top();
if (sir[i] == ')')
{
while (!op.empty() && op.top() != '(')
{
c = op.top();
op.pop();
rez[lgRez++] = ' ';
rez[lgRez++] = c;
rez[lgRez] = NULL;
}
if (op.top() == '(')
{
op.pop();
}
}
else
{
while (compOperatori(c, sir[i]) > 0)
{
op.pop();
rez[lgRez++] = ' ';
rez[lgRez++] = c;
rez[lgRez] = NULL;
if (op.empty())
{
break;
}
c = op.top();
}
op.push(sir[i]);
}
}
}
}
if (lgElem > 0)
{
if (lgRez > 0)
{
strcat(rez, " ");
lgRez++;
}
strcat(rez, elem);
lgRez += lgElem;
// nu mai avem nici un element acum
lgElem = 0;
}
while (!op.empty())
{
c = op.top();
rez[lgRez++] = ' ';
rez[lgRez++] = c;
rez[lgRez] = NULL;
op.pop();
}
return rez;
}
/*
compara doi operatori aritmetici
-1 : x < y
0 : x == y
1 : x > y
*/
int compOperatori(char x, char y)
{
if (x == '*' || x == '/')
{
if (y == '*' || y == '/')
{
return 0;
}
else
{
return 1;
}
}
if (x == '+' || x == '-')
{
if (y == '+' || y == '-')
{
return 0;
}
if (y == '*' || y == '/')
{
return -1;
}
return 1;
}
// stim sigur ca x este (
if (y == '(')
{
return 0;
}
// stim clar ca y are prioritate mai mare fata de x
return -1;
}