Cod sursa(job #941412)

Utilizator andreiagAndrei Galusca andreiag Data 18 aprilie 2013 19:14:17
Problema Evaluarea unei expresii Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 3.08 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;
vector<LL> numbers;

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++;} */
                        { ret += '0';
                         LL n = 0;
                         while (i < s && isdigit(line[i])) {
                            n *= 10; n += line[i] - '0'; i++;}
                         numbers.push_back(n);
                        }

        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 j = 0;
    int s = A.size();
    while(i < s) {
        char c = A[i];
        if (c == '0') {LL n = numbers[j]; factors.push(n); i++; j++;}
        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;
}