Pagini recente » Cod sursa (job #2980074) | Cod sursa (job #753011) | Cod sursa (job #1515830) | Cod sursa (job #937718) | Cod sursa (job #1134123)
// 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,int &);
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);
//cout<<canonical<<endl;
string polish=getPostfixPolish(canonical);
//cout<<polish;
outFile<<evaluate(polish,A);
}
string getCanonicalForm(string E,int A[]){
string aux="";
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,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( 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<char> st;
int l=0;
for(int i=0;i<S.size();i++){
if(S[i]=='o') st.push(A[l++]);
if(S[i]=='+'){
int x=st.top();
st.pop();
int y=st.top();
st.pop();
st.push(y+x);
}
if(S[i]=='-'){
int x=st.top();
st.pop();
int y=st.top();
st.pop();
st.push(y-x);
}
if(S[i]=='*'){
int x=st.top();
st.pop();
int y=st.top();
st.pop();
st.push(y*x);
}
if(S[i]=='/'){
int x=st.top();
st.pop();
int y=st.top();
st.pop();
st.push(y/x);
}
}
return st.top();
}