Pagini recente » Cod sursa (job #2992517) | Cod sursa (job #143747) | Cod sursa (job #2536189) | Cod sursa (job #403039) | Cod sursa (job #1134212)
// Infoarena. Arhiva Educationala. Evaluarea unei Expresii.
// http://www.infoarena.ro/problema/evaluare
#include<iostream>
#include<fstream>
#include<string>
#include<stack>
using namespace std;
string getCanonicalForm(string,long long[]);
string getPostfixPolish(string);
long long evaluate(string S,long long[]);
bool isDigit(char);
long long getNumber(string,unsigned long long &);
long long operatie(long long,long long,char);
int main(){
// freopen("evaluare.in","r",stdin);
// freopen("evaluare.out","w",stdout);
ifstream inFile("evaluare.in");
ofstream outFile("evaluare.out");
string E,e;
getline(inFile,E);
// cout<<E;
long long A[100000];
string canonical=getCanonicalForm(E,A);
//cout<<canonical<<endl;
string polish=getPostfixPolish(canonical);
//cout<<polish;
outFile<<evaluate(polish,A);
}
string getCanonicalForm(string E,long long A[]){
string aux="";
unsigned long long i=0,level=0;
while( i<E.size() ){
if( !isDigit(E[i]) ) aux+=E[i++];
else{
A[level++]=getNumber(E,i);
aux+='o';
}
}
return aux;
}
bool isDigit(char c){
return (c>='0' && c<='9');
}
long long getNumber(string E,unsigned long long &i){
long long aux=0;
while( isDigit(E[i]) ) aux=10*aux+(E[i++]-'0');
return aux;
}
string getPostfixPolish(string S){
stack<char> st;
string p="";
for( unsigned long long i=0;i<S.size();i++ ){
if(S[i]=='o') p+='o';
if(S[i]=='(') st.push('(');
if(S[i]==')'){
while(st.top()!='('){
p+=st.top();
st.pop();
}
st.pop();
}
if(S[i]=='+' || S[i]=='-'){
if(st.empty() || st.top()=='(') st.push(S[i]);
else{
while( !(st.empty() || st.top()=='(') ){
p+=st.top();
st.pop();
}
st.push(S[i]);
}
}
if(S[i]=='*' || S[i]=='/'){
if( st.empty() || st.top()=='(' || st.top()=='+' || st.top()=='-' ) st.push(S[i]);
else{
while( !(st.empty() || st.top()=='(' || st.top()=='+' || st.top()=='-' ) ){
p+=st.top();
st.pop();
}
st.push(S[i]);
}
}
}
while(!st.empty()){
p+=st.top();
st.pop();
}
return p;
}
long long evaluate(string S,long long A[]){
stack<long long> st;
int l=0;
for(unsigned long long i=0;i<S.size();i++){
if(S[i]=='o') st.push(A[l++]);
else{
long long x=st.top();
st.pop();
long long y=st.top();
st.pop();
st.push( operatie(x,y,S[i]) );
}
}
return st.top();
}
long long operatie(long long x,long long y,char c){
switch(c){
case '+': return x+y;
case '-': return x-y;
case '*': return x*y;
case '/': return x/y;
}
return 0;
}