Pagini recente » Cod sursa (job #3353107) | Cod sursa (job #2116773) | Diferente pentru blog/code-golf-logaritm intre reviziile 13 si 12 | Cod sursa (job #877379) | Cod sursa (job #3352482)
#include <fstream>
#include <cstring>
#include <cstdint>
using namespace std;
ifstream f("evaluare.in");
ofstream g("evaluare.out");
const int LMAX = 100005;
char expr[LMAX + 1];
template<typename T>
struct Node
{
T inf;
Node *next;
Node(): inf(0), next(NULL) {}
};
template<typename T>
struct Stack
{
Node<T> *top;
Stack(): top() {}
void Push(T x)
{
if(top == NULL)
{
top = new Node<T>;
top->inf = x;
top->next = NULL;
return;
}
Node<T> *node = new Node<T>;
node->inf = x;
node->next = top;
top = node;
}
void Pop()
{
Node<T> *node = top;
top = top->next;
delete node;
}
inline T Top()
{
return top == NULL ? 0 : top->inf;
}
inline bool Empty()
{
return top == NULL;
}
friend ostream& operator << (ostream& out, const Stack<T>& stack)
{
Node<T> *crt = stack.top;
while(crt != NULL)
{
out << crt->inf << ' ';
crt = crt->next;
}
return out;
}
};
inline bool Operator(char ch)
{
return (ch == '*' || ch == '/' || ch == '+' || ch == '-');
}
int Priority(char ch)
{
if(ch == '+' || ch == '-') return 1;
if(ch == '*' || ch == '/') return 2;
return 0;
}
void Process(Stack<int64_t>& st, Stack<char>& op)
{
char ch = op.Top(); op.Pop();
int64_t right = st.Top(); st.Pop();
int64_t left = st.Top(); st.Pop();
switch(ch)
{
case '*':
st.Push(left * right);
break;
case '/':
st.Push(left / right);
break;
case '+':
st.Push(left + right);
break;
case '-':
st.Push(left - right);
break;
}
}
int64_t Evaluate(char expr[LMAX + 1])
{
Stack<int64_t> st;
Stack<char> op;
for(char *crt = expr; *crt != '\0'; )
{
if(*crt == ' ') crt++;
else if(*crt == '(')
{
op.Push('(');
crt++;
}
else if(Operator(*crt))
{
while(!op.Empty() && Priority(op.Top()) >= Priority(*crt))
Process(st, op);
op.Push(*crt);
crt++;
}
else if(*crt == ')')
{
while(!op.Empty() && op.Top() != '(')
Process(st, op);
crt++;
op.Pop();
}
else
{
int64_t val = 0;
while(isdigit(*crt))
{
val = val * 10 + (*crt - '0');
crt++;
}
st.Push(val);
}
}
while(!op.Empty())
Process(st, op);
return st.Top();
}
int main()
{
f.getline(expr, LMAX + 1);
g << Evaluate(expr) << '\n';
return 0;
}