Pagini recente » Cod sursa (job #1485113) | Cod sursa (job #1054613) | Cod sursa (job #593304) | Cod sursa (job #565832) | Cod sursa (job #1839373)
#include<fstream>
#include<vector>
#include<iostream>
using namespace std;
ifstream in("evaluare.in");
ofstream out("evaluare.out");
char expr[100010];
#define INCORRECT_EXPRESSION 1;
class Expression_evaluator
{
private:
char expr[200010];
vector<int> polish_expr;
vector<int> stk;
int it;
const char Expresion_symbols[8] = { 0,'*','/','+','-','(',')'};
const int Priority_symbols[8] = { 0,4,4,3,3,2,1};
int parse_number(char s[])
{
int nr = 0;
int ok = 0;
while (s[it] >= '0' && s[it] <= '9')
{
nr = nr * 10 + (s[it] - '0');
++it;
ok = 1;
}
if (ok)
return nr;
else
{
for(int i=1;i<=6;++i)
if (s[it] == Expresion_symbols[i])
{
++it;
return -i;
}
throw INCORRECT_EXPRESSION;
}
}
public:
void set_expression(char s[])
{
it = 0;
expr[it++] = '0';
if(s[0]!='\0' && s[0]!='-')
expr[it++] = '+';
for (int i=0; s[i] != '\0'; ++i)
{
expr[it++] = s[i];
if (s[i] == '(')
{
expr[it++] = '0';
if(s[i+1]!='\0' && s[i+1]!='-')
expr[it++] = '+';
}
}
expr[it]='\0';
polish_expr.clear();
stk.clear();
for (it = 0; expr[it] != '\0';)
{
int nr = parse_number(expr);
if (nr>=0)
polish_expr.push_back(nr);
else
{
if (Expresion_symbols[-nr] == ')')
{
while (stk.size() && Expresion_symbols[-stk.back()] != '(')
{
polish_expr.push_back(stk.back());
stk.pop_back();
}
if (stk.size())
stk.pop_back();
else
throw INCORRECT_EXPRESSION;
}
else if (Expresion_symbols[-nr] == '(')
stk.push_back(nr);
else
{
while (stk.size() && Priority_symbols[-stk.back()]>= Priority_symbols[-nr] && Expresion_symbols[-stk.back()]!='(')
{
polish_expr.push_back(stk.back());
stk.pop_back();
}
stk.push_back(nr);
}
}
}
while (stk.size())
{
polish_expr.push_back(stk.back());
stk.pop_back();
}
}
int get_result()
{
int a = 0, b = 0;
stk.clear();
for (int i = 0; i < polish_expr.size(); ++i)
{
if (polish_expr[i] < 0)
{
if (stk.size())
{
b = stk.back();
stk.pop_back();
}
else
throw INCORRECT_EXPRESSION;
if (stk.size())
{
a = stk.back();
stk.pop_back();
}
else
throw INCORRECT_EXPRESSION;
if (Expresion_symbols[-polish_expr[i]] == '+')
{
stk.push_back(a + b);
}
else if (Expresion_symbols[-polish_expr[i]] == '-')
{
stk.push_back(a - b);
}
else if (Expresion_symbols[-polish_expr[i]] == '*')
{
stk.push_back(a*b);
}
else if (Expresion_symbols[-polish_expr[i]] == '/')
{
stk.push_back(a / b);
}
else
{
throw INCORRECT_EXPRESSION;
}
}
else
{
stk.push_back(polish_expr[i]);
}
}
if(stk.size()>1)
throw INCORRECT_EXPRESSION;
return stk.back();
}
};
vector<int> stk;
int main()
{
in >> expr;
Expression_evaluator expression;
try
{
expression.set_expression(expr);
out << expression.get_result();
}
catch (int e)
{
out << "Incorrect expression";
}
return 0;
}