Cod sursa(job #474242)
/* Search your notes :) */
#include <stdio.h>
#include <string.h>
using namespace std;
char sir[100001], stack[10001];
int output[100001], stiva[100001], used[100001], prior[100];
int n, i, j, nr;
int primul, varf;
void initializare ()
{
prior['('] = prior[')'] = 4;
prior['+'] = prior['-'] = 1;
prior['*'] = prior['/'] = 2;
}
void afisare_RPN ()
{
for (i=1; i<=primul; ++i)
if (used[i])
printf ("%c ", output[i]);
else
printf ("%d ", output[i]);
printf ("\n\n");
}
int is_sign (char x)
{
if (x == '+' || x == '-' || x == '*' || x == '/')
return 1;
return 0;
}
int main ()
{
FILE *f = fopen ("evaluare.in","r");
FILE *g = fopen ("evaluare.out","w");
fscanf (f,"%s", sir);
initializare ();
i = 0;
while (sir[i] != '\0')
{
if (sir[i] >= '0' && sir[i] <= '9')
{
while (sir[i] >= '0' && sir[i] <= '9')
{
nr = nr * 10 + sir[i] - '0';
i ++;
}
i --;
primul ++;
output[primul] = nr;
nr = 0;
}
else if (sir[i] == '(')
{
varf ++;
stack[varf] = '(';
}
else if (sir[i] == ')')
{
while (stack[varf] != '(')
{
primul ++;
output[primul] = stack[varf];
stack[varf] = 0;
if (is_sign (output[primul]))
used[primul] = 1;
varf --;
}
stack[varf] = 0;
varf --;
}
else if (is_sign (sir[i]))
{
while (prior[sir[i]] <= prior[stack[varf]] && prior[stack[varf]] != prior['(']) /* while !!! - cat timp gaseste <= scoate */
{
primul ++;
output[primul] = stack[varf];
if (is_sign (output[primul]))
used[primul] = 1;
stack[varf] = sir[i];
varf --;
}
varf ++; /* apoi bagam asta in stiva */
stack[varf] = sir[i];
}
i ++;
}
while (varf)
{
primul ++;
output[primul] = stack[varf];
if (is_sign (output[primul]))
used[primul] = 1;
varf --;
}
varf = 0;
for (i=1; i<=primul; ++i)
{
if (used[i])
{
if (output[i] == '+')
stiva[varf-1] += stiva[varf];
else if (output[i] == '-')
stiva[varf-1] -= stiva[varf];
else if (output[i] == '*')
stiva[varf-1] *= stiva[varf];
else if (output[i] == '/')
stiva[varf-1] /= stiva[varf];
varf --;
}
else
{
varf ++;
stiva[varf] = output[i];
}
}
fprintf (g, "%d\n", stiva[1]);
fclose (g);
fclose (f);
return 0;
}