Pagini recente » Cod sursa (job #191240) | Cod sursa (job #2831814) | Profil Lumine | Monitorul de evaluare | Cod sursa (job #2720736)
#include <iostream>
#include <fstream>
#include <vector>
#include <string.h>
#define maxL 100000
using namespace std;
ifstream f("evaluare.in");
ofstream o("evaluare.out");
struct token
{
bool isDig;
union
{
int number;
char op;
} data;
};
int prec(char op)
{
if (op == '+' || op == '-')
return 0;
return 1;
}
int greaterPrec(char op1, char op2)
{
return prec(op1) - prec(op2);
}
bool isOp(char op)
{
return op == '+' || op == '-' || op == '*' || op == '/';
}
bool isLeftAssoc(char op)
{
return true; // all of our operators are left associative
}
void toRPN(char exp[], int len, vector<token> &output)
{
vector<char> operators;
token aux;
int num;
for (int i = 0; i < len; i++)
{
if (isdigit(exp[i]))
{
num = exp[i] - '0';
while (isdigit(exp[++i]))
{
num = num * 10 + (exp[i] - '0');
}
aux.isDig = 1;
aux.data.number = num;
output.push_back(aux);
i--;
}
else
{
// is an operator
if (isOp(exp[i]))
{
while (!operators.empty() && ((greaterPrec(operators.back(), exp[i]) > 0) || (greaterPrec(operators.back(), exp[i]) == 0 && isLeftAssoc(exp[i]))) && (operators.back() != '('))
{
aux.isDig = 0;
aux.data.op = operators.back();
output.push_back(aux);
operators.pop_back();
}
operators.push_back(exp[i]);
}
else
{
if (exp[i] == '(')
{
operators.push_back('(');
}
else
{
while (operators.back() != '(')
{
aux.isDig = 0;
aux.data.op = operators.back();
output.push_back(aux);
operators.pop_back();
}
operators.pop_back();
}
}
}
}
aux.isDig = 0;
while (!operators.empty())
{
aux.data.op = operators.back();
output.push_back(aux);
operators.pop_back();
}
}
int eval(int a, int b, char op)
{
if (op == '+')
return a + b;
if (op == '-')
return a - b;
if (op == '*')
return a * b;
return a / b;
}
int solveRPN(vector<token> polish)
{
vector<int> stack;
int a, b;
for (vector<token>::iterator i = polish.begin(); i != polish.end(); ++i)
{
if (i->isDig)
{
stack.push_back(i->data.number);
}
else
{
a = stack.back();
stack.pop_back();
b = stack.back();
stack.pop_back();
stack.push_back(eval(b, a, i->data.op));
}
}
return stack.back();
}
int main()
{
char exp[maxL];
int len;
f >> exp;
len = strlen(exp);
vector<token> output;
toRPN(exp, len, output);
for (vector<token>::iterator i = output.begin(); i != output.end(); ++i)
{
if (i->isDig)
cout << i->data.number;
else
cout << i->data.op;
cout << " ";
}
o << solveRPN(output);
}