Cod sursa(job #2198627)

Utilizator danielsociuSociu Daniel danielsociu Data 24 aprilie 2018 20:46:07
Problema Evaluarea unei expresii Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 3.62 kb
#include <fstream>
#include <vector>
#include <cstdlib>
#include <string>
#include <cstring>
using namespace std;
ifstream cin("evaluare.in");
ofstream cout("evaluare.out");
#define max 100001
#define EMPTY 0
struct stacks{ char X[max]; int top;};

int isempty(stacks *st){
    return (st->top==EMPTY)?1:0;
}
void EMPTYstack(stacks *st){
    st->top=EMPTY;
}
void push(stacks *st, char x){
    st->X[++st->top]=x;
}

char pop(stacks *st){
    char ret=(char)EMPTY;
    if(!isempty(st))
    {
        ret=st->X[st->top];
        st->top--;
    }
    return ret;
}

int isoperator(char x){
    if(x=='*'||x=='/'||x=='+'||x=='-'||x=='%'||x=='^')
        return 1;
    return 0;
}
int priority(char x){
    int p=0;
    if(x=='*'||x=='/')
        p=2;
    else if(x=='+'||x=='-')
        p=1;
    return p;
}

void infix2postfix(char *infix, char*postfix, int innerspace){
    char *i;
    char *p;
    char n1;
    stacks st;
    EMPTYstack(&st);
    i=&infix[0];
    p=&postfix[0];
    while(*i){
        if(*i==' '||*i=='\t'){
            while(*i==' '||*i=='\t'){
                i++;
            }
        }
        if(isdigit(*i)||isalpha(*i)){
            while(isdigit(*i)||isalpha(*i)){
                *p=*i;
                i++;p++;
            }
            if(innerspace){
                *p=' ';
                p++;
            }
        }
        if(*i=='('){
            push(&st,*i);
            i++;
           }
        if(*i==')'){
            n1=pop(&st);
            while(n1!='(')
            {
                *p=n1;
                p++;
                if(innerspace){
                    *p=' ';
                    p++;
                }
                n1=pop(&st);
            }
            i++;
        }
        if(isoperator(*i)){
            if(isempty(&st))
                push(&st,*i);
            else{
                n1=pop(&st);
                while(priority(n1)>=priority(*i)){
                    *p=n1;
                    p++;
                    if(innerspace){
                        *p=' ';
                        p++;
                    }
                    n1=pop(&st);
                }
                push(&st,n1);
                push(&st,*i);
            }
        i++;
        }
    }
    while(!isempty(&st)){
        n1=pop(&st);
        *p=n1;
        p++;
        if(innerspace){
            *p=' ';
            p++;
        }
    }
    *p=NULL;
}

int evaluare(char *post){
    char *p=&post[0];
    char number[15];
    int v[max/2], top=-1;
    while(*p){
        if(*p==' '||*p=='\t')
            p++;
        if(isoperator(*p)){
            int op1=v[top];
            int op2=v[--top];
            switch(*p){
                case '+':
                    v[top]=op1+op2;
                    break;
                case '-':
                    v[top]=op2-op1;
                    break;
                case '/':
                    v[top]=op2/op1;
                    break;
                case '*':
                    v[top]=op1*op2;
                    break;
                default:
                    return -1;
            }
            p++;
        }
        else{
            int i=-1;
            while(isdigit(*p)||isalpha(*p)){
                number[++i]=*p;
                p++;
            }
            number[++i]=NULL;
            v[++top]=atoi(number);
        }
        p++;
    }
    return v[0];

}

int main(){
    char in[max]={0}, post[max]={0};
    cin>>in;
    infix2postfix(&in[0],&post[0],1);
    cout<<evaluare(&post[0]);
    return 0;
}