Cod sursa(job #2233360)

Utilizator SagunistuStrimbu Alexandru Sagunistu Data 23 august 2018 00:27:50
Problema Evaluarea unei expresii Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 4.25 kb
#include <fstream>
#include <iostream>
#include <stack>
#include <ctype.h>
#include <map>

using namespace std;

class cTree
{
    private:
        int m_value;
        cTree* m_left;
        cTree* m_right;
        bool m_isLeaf;
    public:
        cTree(int value, cTree* left, cTree* right, bool isLeaf);
        ~cTree(){}
        int getValue() { return m_value; }
        cTree* getLeft() { return m_left; }
        cTree* getRight() { return m_right; }
        bool isLeaf() { return m_isLeaf; }
};

cTree::cTree(int value, cTree* left, cTree* right, bool isLeaf)
:m_value(value), m_left(left), m_right(right), m_isLeaf(isLeaf){}

class cExpressionTree
{
private:
    cTree* tree;
public:
    cExpressionTree(std::string expression);
    ~cExpressionTree();
    cTree* getTree() { return tree; }
    int getExpressionValue();
private:
    cTree* generateTree(std::string expression);
    int priority(char c);
    int inorderValues(cTree* node);
};

cExpressionTree::cExpressionTree(std::string expression)
{
    tree = generateTree(expression);
}

int cExpressionTree::priority(char c) {
    if(c == '*' || c == '/')
        return 2;
    if(c =='+' || c == '-')
        return 1;
    return 0;
}

cTree* cExpressionTree::generateTree(std::string expression)
{
    expression = "(" + expression + ")";
    std::stack<char> operatorStack;
    std::stack<cTree*> operandStack;
    int ident = -1;
    int counter = 0;
    for(std::string::iterator ii = expression.begin(); ii != expression.end(); ++ii) {
        int size = 0;
        char c = *ii;
        if(isdigit(c)) {
            if(ident == -1)
                ident = 0;
            ident = ident * 10 + (c - '0') ;
        }
        else {
            if(ident >= 0)
            operandStack.push(new cTree(ident, nullptr, nullptr, true));
            size = operandStack.size();
            ident = -1;
            if(c == '/' || c =='*' || c == ')' || c == '-' || c == '+') {
                char ceva = operatorStack.top();
                int priorityc = priority(c);
                int priorityceva = priority(ceva);
                while(!operatorStack.empty() && priority(c) <= priority(operatorStack.top())) {
                    char top = operatorStack.top();
                    operatorStack.pop();
                    if(top != '(') {
                        cTree* right = operandStack.top();
                        operandStack.pop();
                        cTree* left = operandStack.top();
                        operandStack.pop();
                        operandStack.push(new cTree((int)top, left, right, false));
                    }
                    else
                        break;
                }
                if(c != ')') {
                    operatorStack.push(c);
                }
            }
            else
            if(c == '(') {
                operatorStack.push(c);
            }
        }
    }
    cTree *res = operandStack.top();
    operandStack.pop();
    if(operandStack.size()>0)
        cout << operandStack.size() << endl;
    return res;
}

int cExpressionTree::getExpressionValue() {
    return inorderValues(tree);
}

int cExpressionTree::inorderValues(cTree* node) {
    if(node->isLeaf()) {
        return node->getValue();
    }
    if(node->getValue() == '+') {
        return inorderValues(node->getLeft()) + inorderValues(node->getRight());
    }
     if(node->getValue() == '-') {
        return inorderValues(node->getLeft()) - inorderValues(node->getRight());
    }
     if(node->getValue() == '*') {
        return inorderValues(node->getLeft()) * inorderValues(node->getRight());
    }
    return inorderValues(node->getLeft()) / inorderValues(node->getRight());
}

void inorder(cTree* tree) {
    if(tree == nullptr)
        return;
    inorder(tree->getLeft());
    inorder(tree->getRight());
    if(tree->isLeaf())
        cout << tree->getValue() << " ";
    else
        cout << (char)(tree->getValue()) << " ";
}

int main()
{
    ifstream fin("evaluare.in");
    ofstream fout("evaluare.out");
    string value;
    fin >> value;
    cExpressionTree* tree = new cExpressionTree(value);
    inorder(tree->getTree());
    fout << tree->getExpressionValue();
    return 0;
}