Cod sursa(job #2213646)

Utilizator AlexDabuDabu Alexandru AlexDabu Data 16 iunie 2018 18:57:33
Problema Evaluarea unei expresii Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 2.38 kb
/*
Evaluarea unei expresii - dupa o idee de Sima Cotizo (job ID 144801)

Definim recursiv o expresie de nivel k (k>=0) astfel:
E(k) = E1(k+1) o(k) E2(k+1) o(k) ... o(k) En(k+1)
unde Ei(k+1) sunt expresii de nivel k+1, iar
o(k) sunt operatori cu nivel de prioritate k

Ultimul nivel din expresii (fie acesta L) este alcatuit
din variabile sau expresii de nivel 0 incluse intr-o pereche de paranteze
E(L) = x (x variabila sau numar) sau E(L) = ( E(0) )

Vom evalua astfel expresiile pe niveluri de prioritate, folosind in
fiecare nivel operatorii din clasa de prioritate respectiva
*/

#include <cstdio>
#include <cstring>
#include <iostream>
#include <fstream>

using namespace std;

ifstream fin("evaluare.in");
ofstream fout("evaluare.out");

#define LMAX 2 // nivelul maxim de prioritate
char op[4][4] = { "+-", "*/", "^", "" }; // operatorii pe niveluri de prioritate

#define NX 100010
char S[NX], *p = S;

int eval(int a, int b, char o) {
	switch (o) {
	case '+': return a + b;
	case '-': return a - b;
	case '*': return a * b;
	case '/': return a / b;
	}
}

/*
Urmatoarea functie evalueaza expresia care incepe pe pozitie indicata de p
considerand ca aceasta este de nivel lev

Daca am ajuns pe ultimul nivel, studiem cele doua cazuri pentru E(L) :
* poate urma o expresie de nivel 0 intre paranteze: (E(0))
* poate urma o constanta (pentru alte probleme si o variabila)

In primul caz, trecem peste '(', evaluam E(0) si trecem peste ')'.
In cel de-al doilea caz, citim numarul, cifra cu cifra

Daca nu suntem pe ultimul nivel, vom evalua expresia
E1(lev+1) op(lev) E2(lev+1) op(lev)...

Initial, x va fi E1(lev+1), apoi, la al i-ulea operator op(lev) intalnit
x = E1(lev+1) op(lev) ... op(lev) Ei(lev+1)
y = x op(lev) E_i+1_(lev+1)

Cand trimitem parametrii functiei eval, pointerul p este incrementat
inainte de apelul recursiv
*/

int expr(int lev) {
	int x, y;
	if (lev == LMAX)
		if (*p == '(')
			++p, x = expr(0), ++p;
		else
			for (x = 0; *p >= '0' && *p <= '9'; ++p)
				x = x * 10 + *p - '0';
	else
		for (x = expr(lev + 1); strchr(op[lev], *p); x = y)
			y = eval(x, expr(lev + 1), *p++), cout << "y = " << y << endl;
	return x;
}

void Read()
{
	int index = 0;
	while (fin >> S[index])
	{
		index++;
	}
	S[index] = ' ';
}

void Print()
{
	fout << expr(0);
}

int main() 
{
	Read();
	Print();
	getchar();
	return 0;
}