Pagini recente » Istoria paginii runda/ichb-locala-2013-10 | Planificare infoarena | Cod sursa (job #3298082)
#include <fstream>
#include <string>
#include <vector>
#include <unordered_map>
#include <stack>
#include <cctype>
#include <climits>
using namespace std;
ifstream fin("evaluare.in");
ofstream fout("evaluare.out");
vector<string> polo;
unordered_map<char, int> um = {
{'+', 1},
{'-', 1},
{'*', 10},
{'/', 10}
};
struct nod{
string vf;
nod *fs = NULL;
nod *fd = NULL;
};
nod *arb(const vector<int>& p, const vector<string>& e)
{
nod *n = new nod;
int mini = INT_MAX;
int pos = 0;
for(int i = 0 ; i < p.size() ; i++)
if(p[i] < mini)
{
mini = p[i];
pos = i;
}
n->vf = e[pos];
if(p.size() == 1)
return n;
n->fs = arb(vector<int>(p.begin(), p.begin() + pos), vector<string>(e.begin(), e.begin() + pos));
n->fd = arb(vector<int>(p.begin() + pos + 1, p.end()), vector<string>(e.begin() + pos + 1, e.end()));
return n;
}
void SDR(nod *root)
{
if(!root)
return;
if(root->fs)
SDR(root->fs);
if(root->fd)
SDR(root->fd);
polo.push_back(root->vf);
}
int main()
{
string expresie;
fin >> expresie;
vector<string> e;
vector<int> p;
int c = 0;
char t;
for(int i = 0 ; i < expresie.size() ; i++)
{
if(expresie[i] == '(')
{
c += 100;
continue;
}
if(expresie[i] == ')')
{
c -= 100;
continue;
}
if(isdigit(expresie[i]))
{
string numar(1, expresie[i]);
int j = i + 1;
while(j < expresie.size() && isdigit(expresie[j]))
{
numar += expresie[j];
j++;
}
i = j - 1;
e.push_back(numar);
p.push_back(100000);
}
else
{
e.push_back(string(1, expresie[i]));
p.push_back(um[expresie[i]] + c);
}
}
nod *root = arb(p, e);
SDR(root);
stack<int> rez;
for(auto it : polo)
{
if(it != "+" && it != "-" && it != "/" && it != "*")
rez.push(stoi(it));
else
{
int b = rez.top(); rez.pop();
int a = rez.top(); rez.pop();
if(it == "+")
rez.push(a + b);
if(it == "-")
rez.push(a - b);
if(it == "*")
rez.push(a * b);
if(it == "/")
rez.push(a / b);
}
}
fout << rez.top();
}