Cod sursa(job #1732045)

Utilizator alex.bullzAlexandru Lilian alex.bullz Data 20 iulie 2016 17:06:06
Problema Evaluarea unei expresii Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 3.5 kb
#include <fstream>
#include <iostream>
#include <string>
#include <vector>
#include <stack>
#include <unordered_map>
#include <utility>
#include <assert.h>

char str[100000];
std::unordered_map<char, int> precedence;

bool is_operator (char a) {
    if (    a == '+' || 
            a == '-' ||
            a == '*' ||
            a == '/' ||
            a == '^') {
        return true;
    }
    
    return false;
}

std::string infix_to_postfix (std::string infix) {
    int size = infix.length();
    std::stack <char> stack;
    bool ok = false;
    std::string postfix;

    int num = 0;
    for (int i = 0; i < size; ++i) {
        if (infix[i] == ' ') {
            continue;
        }

        while (infix[i] >= '0' && infix[i] <= '9') {
            ok = true;
            num = num * 10 + (infix[i] - '0');
            ++i;
        }

        if (ok) {
            postfix += std::to_string (num);
            postfix += " ";
            ok = false;
            num = 0;
        }

        if (infix[i] == '(') {
            stack.push (infix[i]);
            continue;
        }

        if (is_operator (infix[i])) {
                while (!stack.empty() && is_operator (stack.top()) &&
                        precedence[infix[i]] <= precedence[stack.top()]) {
                    postfix += stack.top();
                    postfix += " ";
                    stack.pop();
                }
            stack.push (infix[i]);
            continue;
        }

        if (infix[i] == ')') {
            while (is_operator (stack.top())) {
                postfix += stack.top();
                postfix += " ";
                stack.pop();
            }

            assert (stack.top() == '(');
            stack.pop();
            continue;
        }
    }

    while (!stack.empty()) {
        assert (is_operator (stack.top()));
        postfix += stack.top();
        postfix += " ";
        stack.pop();
    }

    return postfix;
}

long do_op (int a, int b, char op) {
    switch (op) {
    case '+':
        return a + b;
        break;
    case '-':
        return a - b;
        break;
    case '*':
        return a * b;
        break;
    case '/':
        return (float)a / b;
        break;
    default:
        return -1.0;
    }
}

long evaluate (std::string postfix) {
    int size = postfix.size();
    int num = 0;
    bool ok = false;
    std::stack <long> stack;

    for (int i = 0; i < size; ++i) {
        while (postfix[i] >= '0' && postfix[i] <= '9') {
            ok = true;
            num = num * 10 + (postfix[i] - '0');
            ++i;
        }

        if (ok) {
            stack.push (num);
            ok = false;
            num = 0;
        }

        if (is_operator (postfix[i])) {
            assert (stack.size() >= 2);
            int o1, o2;
            o1 = stack.top();
            stack.pop();
            o2 = stack.top();
            stack.pop();

            stack.push (do_op (o2, o1, postfix[i]));
        }
    }

    assert (stack.size() == 1);
    return stack.top();
}

int main() {
    precedence.insert (std::pair<char, int> ('+', 1));
    precedence.insert (std::pair<char, int> ('-', 1));
    precedence.insert (std::pair<char, int> ('*', 2));
    precedence.insert (std::pair<char, int> ('/', 2));
    precedence.insert (std::pair<char, int> ('^', 3));

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

    fin.getline (str, 100000);
    std::string infix (str);

    fout << evaluate (infix_to_postfix (infix)) << "\n";
    fout.close();
    fin.close();

    return 0;
}