Cod sursa(job #1462885)

Utilizator sorynsooSorin Soo sorynsoo Data 19 iulie 2015 12:55:13
Problema Evaluarea unei expresii Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.32 kb
//Evaluare expresie cu transformare in forma poloneza
#include <fstream>
#include <stack>
#include <vector>
#include <string.h>
using namespace std;

ifstream cin("evaluare.in");
ofstream cout("evaluare.out");
#define MAXSIR 100005

char sir[MAXSIR],expr[MAXSIR][15];
int n;

int prioritate(char semn)
{
    if(semn == '(' || semn == ')')
        return 0;
    if(semn == '+' || semn == '-')
        return 1;
    if(semn == '*' || semn=='/')
        return 2;
}
void to_polish(char sir[], char expr[MAXSIR][15])
{
    stack<char> st;
    int lim,i,j;
    lim=strlen(sir);
    for(i=0; i<lim; i++)
    {
        if(sir[i]=='(')
        {
            st.push('(');
            continue;
        }

        if(isdigit(sir[i]))
        {
            int c=0;
            while(isdigit(sir[i]))
                expr[n][c++]=sir[i++];


            i--; n++;
            continue;
        }

        if(sir[i]==')')
        {
            while(!st.empty() && st.top()!='(')
            {
                expr[n++][0]=st.top();
                st.pop();
            }
            st.pop();
            continue;
        }

        if(sir[i]=='+' || sir[i]=='-' || sir[i]=='*' || sir[i]=='/')
        {
            while(!st.empty() && prioritate(st.top()) >= prioritate(sir[i]))
            {
                expr[n++][0]=st.top();
                st.pop();
            }
            st.push(sir[i]);
        }
    }
    while(!st.empty())
    {
         expr[n++][0]=st.top();
         st.pop();
    }
}
int eval_expr(char expr[MAXSIR][15])
{
    stack<int> st;
    for(int i=0; i<n; i++)
    {
        if(isdigit(expr[i][0]))
        {
            int nr=0,c=0;
            while(isdigit(expr[i][c]))
                nr=nr*10+expr[i][c++]-'0';

            st.push(nr);
        }
        else
        {
            int a=st.top(); st.pop();
            int b=st.top(); st.pop();
            if(expr[i][0]=='+')
                st.push(b+a);
            if(expr[i][0]=='-')
                st.push(b-a);
            if(expr[i][0]=='*')
                st.push(b*a);
            if(expr[i][0]=='/')
                st.push(b/a);
        }
    }
    return st.top();


}
int main()
{
    cin.getline(sir,MAXSIR);
    to_polish(sir,expr);
    cout<<eval_expr(expr);

}