Pagini recente » Cod sursa (job #1282041) | Cod sursa (job #3201219) | Cod sursa (job #940025) | Cod sursa (job #1123092) | Cod sursa (job #1134255)
// 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,int[]);
string getPostfixPolish(string);
int evaluate(string S,int[]);
bool isDigit(char);
int getNumber(string,unsigned int &);
int operatie(int,int,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;
int A[100000];
string canonical=getCanonicalForm(E,A);
string polish=getPostfixPolish(canonical);
outFile<<evaluate(polish,A);
}
string getCanonicalForm(string E, int A[]){
string aux="";
unsigned int 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');
}
int getNumber(string E,unsigned int &i){
int 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 int 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;
}
int evaluate(string S,int A[]){
stack<int> st;
int l=0;
for(unsigned int i=0;i<S.size();i++){
if(S[i]=='o') st.push(A[l++]);
else{
int x=st.top();
st.pop();
int y=st.top();
st.pop();
st.push( operatie(x,y,S[i]) );
}
}
return st.top();
}
int operatie(int x,int y,char c){
switch(c){
case '+': return y+x;
case '-': return y-x;
case '*': return y*x;
case '/': return y/x;
}
return 0;
}