Cod sursa(job #477633)
/* Rezolvare folosind recursivitatea indirecta (transformare RPN) si evaluarea expresiei RPN
** Autor : Cosmina Albulescu (miculprogramator)
** IDE : Code :: Blocks
*/
#include <stdio.h>
#include <string.h>
using namespace std;
char e[100001];
int prior[20], rpn[100001], used[100001], stack[10001];
int lg, i, k;
int varf;
void transformare_expresie (); // transforma expresia in RPN
void transformare_termen (); // transforma termenul in RPN
void transformare_factor (); // transforma factorul in RPN
int e_operator (char ch)
{
if (ch >= '0' && ch <= '9')
return 1;
return 0;
}
void initializare ()
{
prior['+'] = prior['-'] = 1;
prior['*'] = prior['/'] = 2;
}
void transformare_factor ()
{
if (e[i] == '(')
{
i ++; // trec peste (
transformare_expresie (); // evaluez expresia dintre ( )
i ++; // trec peste )
}
else
{
k ++;
while (e_operator (e[i]))
{
rpn[k] = rpn[k] * 10 + e[i] - '0'; // introduc factorul in rpn
i ++; // trec la urmatorul factor
}
}
}
void transformare_termen ()
{
int ch;
transformare_factor (); // transform primul factor
while (i < lg && prior[e[i]] == 2) // cat timp mai urmeaza factori
{
ch = e[i]; // retin semnul (* sau /)
i ++;
transformare_factor (); // trec la factorii urmatori
k ++;
rpn[k] = ch;
used[k] = 1;
}
}
void transformare_expresie ()
{
int ch;
transformare_termen (); // transform primul termen
while (i < lg && prior[e[i]] == 1) //cat timp mai am termeni
{
ch = e[i]; // retin semnul (+ sau -)
i ++;
transformare_termen (); // trec la termenii urmatori
k ++;
rpn[k] = ch;
used[k] = 1;
}
}
void afisare_rpn ()
{
for (i=1; i<=k; ++i)
if (used[i])
printf ("%c ", rpn[i]);
else
printf ("%d ", rpn[i]);
}
int main ()
{
FILE *f = fopen ("evaluare.in","r");
FILE *g = fopen ("evaluare.out","w");
fscanf (f,"%s", e);
lg = strlen (e);
initializare ();
transformare_expresie ();
//afisare_rpn ();
i = 1;
while (i <= k) // evaluam RPN
{
if (used[i])
{
if (rpn[i] == '+')
stack[varf-1] += stack[varf];
if (rpn[i] == '-')
stack[varf-1] -= stack[varf];
if (rpn[i] == '*')
stack[varf-1] *= stack[varf];
if (rpn[i] == '/')
stack[varf-1] /= stack[varf];
varf --;
}
else
{
varf ++;
stack[varf] = rpn[i];
}
i ++;
}
fprintf (g, "%d", stack[1]);
fclose (g);
fclose (f);
return 0;
}