Mai intai trebuie sa te autentifici.
Cod sursa(job #2016720)
Utilizator | Data | 30 august 2017 10:19:46 | |
---|---|---|---|
Problema | Evaluarea unei expresii | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 2.98 kb |
#include <cstdio>
#include <vector>
#include <stack>
#include <iostream>
using namespace std;
FILE *in,*out;
const int nmax = 100000;
char c[nmax+3];
struct Symbol
{
int tip;
char semn;
int val;
int prior;
} v[1+nmax];
int n;
int prioritate(char x)
{
if(x == '-' || x == '+')
return 1;
return 2;
}
void parsare()
{
int i = 0, nr = 0, flag = 0;
while(c[i] != '\0')
{
if(c[i] >= '0' && c[i] <= '9') {
if(flag == 0) {
flag = 1;
nr = c[i] - '0';
} else {
nr *= 10;
nr += (c[i] - '0');
}
} else {
if(flag == 1) {
flag = 0;
v[++n].tip = 4;
v[n].val = nr;
}
if(c[i] == '-' || c[i] == '+' || c[i] == '*' || c[i] == '/')
{
v[++n].tip = 3;
v[n].semn = c[i];
v[n].prior = prioritate(c[i]);
}
else if(c[i] == '(')
v[++n].tip = 1;
else if(c[i] == ')')
v[++n].tip = 2;
}
i ++;
}
if(flag == 1) {
v[++n].tip = 4;
v[n].val = nr;
}
}
stack <int> opst;
vector <int> output;
//Ai + * si vii cu un -
void converttopostfix() {
for(int i = 1;i <= n;i ++) {
if(v[i].tip == 3) {
while(0 < opst.size() && v[opst.top()].tip != 1 && v[opst.top()].prior >= v[i].prior) {
output.push_back(opst.top());
opst.pop();
}
opst.push(i);
} else if(v[i].tip == 1) {
opst.push(i);
} else if(v[i].tip == 2) {
while(v[opst.top()].tip != 1) {
output.push_back(opst.top());
opst.pop();
}
opst.pop();
} else if(v[i].tip == 4)
output.push_back(i);
}
while(opst.size() > 0) {
output.push_back(opst.top());
opst.pop();
}
}
int computepostfix() {
if(output.size() == 1) {
return v[output[0]].val;
} else {
int eval[1 + nmax];
int neval = 2;
eval[1] = v[output[0]].val;
eval[2] = v[output[1]].val;
for(int i = 2; i < output.size(); i ++) {
if(v[output[i]].tip == 3) {
if(v[output[i]].semn == '+') {
eval[neval - 1] += eval[neval];
neval--;
} else if(v[output[i]].semn == '-') {
eval[neval - 1] -= eval[neval];
neval--;
} else if(v[output[i]].semn == '*') {
eval[neval - 1] *= eval[neval];
neval--;
} else if(v[output[i]].semn == '/') {
eval[neval - 1] /= eval[neval];
neval--;
}
} else {
eval[++neval] = v[output[i]].val;
}
}
return eval[1];
}
}
int main()
{
in = fopen("evaluare.in","r");
out = fopen("evaluare.out","w");
fgets(c,nmax+3,in);
parsare();
converttopostfix();
fprintf(out,"%d",computepostfix());
return 0;
}