Cod sursa(job #941407)

Utilizator andreiagAndrei Galusca andreiag Data 18 aprilie 2013 18:53:26
Problema Evaluarea unei expresii Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 2.84 kb
// evaluare Polish-expression and stack
#include <string>
#include <stack>
#include <vector>
#include <iostream>
#include <cstdio>
#include <fstream>
#include <cctype>

using namespace std;
typedef long long LL;

stack<char> operations;
stack<LL> factors;

bool is_oper(char c) {
    return (c =='-') || (c == '+') || (c == '*') || (c == '/');
}

bool is_par(char c) {
    return ((c == '(') || (c == ')'));
}

bool high_prec(char c, char d) {
    if ((c == '*' || c == '/') && (d == '+' || d == '-')) return true;
    return false;
}

string process_line(string &line) {
    operations.push('!');
    string ret;
    int i = 0;
    int s = line.size();
    //operations.clear();
    while(i < s){
        //cout << i << endl;

        char c = line[i];
        //cout << c << endl;
        if (isdigit(c)) if(i > 0 && !isdigit(line[i-1])) {ret += ' '; ret += c; i++;}
                        else {ret += c; i++;}
        else if (is_par(c)) {if (c == '(') {operations.push(c); i++;}
                       else {c = operations.top();
                             while (c != '(') {
                                ret += c;
                                operations.pop();
                                c = operations.top();
                             }
                             operations.pop();
                             i++;
                            }
                       }
        else  {char d = operations.top();
                    while(d != '!' && d != '(' && !high_prec(c,d)) {
                    ret += d; operations.pop(); d = operations.top();
                    }
                    operations.push(c); i++;
                    }
        //cout << ret << " : " << operations.top() << endl;
    }
    while(operations.top() != '!') {
        char c = operations.top(); if (c != ')') ret += c;
        operations.pop();
    }
    return ret;
}

LL eval_str(string &A)
{
    LL ret = 0;
    int i = 0;
    int s = A.size();
    while(i < s) {
        char c = A[i];
        if (c == ' ') {
            LL n = 0; i++; c = A[i];
            while(isdigit(c)) {n *= 10; n += c - '0'; i++; c = A[i];}
            factors.push(n);
        }
        else if (is_oper(c)) {
            LL n = factors.top(); factors.pop(); LL m = factors.top(); factors.pop();
            if (c == '+')      m += n;
            else if (c == '-') m -= n;
            else if (c == '*') m *= n;
            else if (c == '/') m /= n;
            factors.push(m);
            i++;
            }
    }
    ret = factors.top();
    return ret;
}

int main()
{
    string line;
    LL n;

    ifstream fin ("evaluare.in");
    ofstream fout("evaluare.out");

    getline(fin, line);

    string RPN = process_line(line);
    LL result = eval_str(RPN);
    fout << result << endl;

    return 0;
}