Pagini recente » Cod sursa (job #1153657) | Cod sursa (job #2298395) | Cod sursa (job #1101721) | Cod sursa (job #879683) | Cod sursa (job #880215)
Cod sursa(job #880215)
#include <fstream>
#include <stack>
#include <cstring>
using namespace std;
ifstream in("evaluare.in");
ofstream out("evaluare.out");
char expr[100001]; int polish[100001];
int opcode[5] = { 0, 1e9 + 1, 1e9 + 2, 1e9 + 3, 1e9 + 4 }; // + - * /
int iD = 0, iS = 0;
int op_prec(const char &op)
{
switch (op)
{
case '*': case '/':
return 2;
case '+': case '-':
return 1;
case '(':
return -1;
}
return 0;
}
int op_code(const char &op)
{
switch (op)
{
case '+': return opcode[1];
case '-': return opcode[2];
case '*': return opcode[3];
case '/': return opcode[4];
}
return 0;
}
void ShuntingYard(int *dest, char *source)
{
int len = strlen(source);
stack<char> ops; // Stiva operatorilor
while (iS < len)
{
if (isdigit(source[iS]))
{
int number = 0;
while (isdigit(source[iS]))
{
number = number * 10 + (source[iS] - 48);
iS++;
}
dest[iD++] = number; continue;
}
else if (source[iS] == '(') ops.push(source[iS]);
else if (source[iS] == ')')
{
char op = ops.top(); ops.pop();
while (op != '(')
{
dest[iD++] = op_code(op);
op = ops.top(); ops.pop();
}
}
else
{
char op1, op2;
op1 = source[iS];
if (!ops.empty())
{
op2 = ops.top();
while (op_prec(op1) <= op_prec(op2))
{
ops.pop();
dest[iD++] = op_code(op2);
if (ops.empty()) break;
op2 = ops.top();
}
}
ops.push(op1);
}
iS++; // next token
}
while (!ops.empty())
{
dest[iD++] = op_code(ops.top());
ops.pop();
}
}
int main()
{
stack<int> eval;
in.getline(expr, 100001);
ShuntingYard(polish, expr);
for (int i = 0; i < iD; i++)
{
if (polish[i] <= int(1e9)) eval.push(polish[i]);
else
{
switch (polish[i] % int(1e9))
{
case 1: {
int ope1 = eval.top(); eval.pop();
int ope2 = eval.top(); eval.pop();
int res = ope1 + ope2;
eval.push(res);
} break;
case 2: {
int ope2 = eval.top(); eval.pop();
int ope1 = eval.top(); eval.pop();
int res = ope1 - ope2;
eval.push(res);
} break;
case 3: {
int ope2 = eval.top(); eval.pop();
int ope1 = eval.top(); eval.pop();
int res = ope1 * ope2;
eval.push(res);
} break;
case 4: {
int ope2 = eval.top(); eval.pop();
int ope1 = eval.top(); eval.pop();
int res = ope1 / ope2;
eval.push(res);
} break;
}
}
}
out << eval.top();
return 0;
}