Cod sursa(job #3304351)

Utilizator robigiirimias robert robigi Data 22 iulie 2025 20:29:47
Problema Evaluarea unei expresii Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3.91 kb
#include <fstream>
#include <vector>
#include <stack>
#include <queue>
#include <cassert>
#include <string>

using namespace std;

enum class TokenType { Number, Operator };

struct Token
{
    TokenType type;
    char op;
    int value;

    Token(int v) : type(TokenType::Number), op(0), value(v) {}
    Token(char o) : type(TokenType::Operator), op(o), value(0) {}
};

struct Node
{
    Token token;
    char op;
    int value;

    Node* left, * right;
    Node(int v) : token(Token(v)), op(0), value(v), left(nullptr), right(nullptr) {}
    Node(char o, Node* l, Node* r) : token(Token(o)), op(o), value(0), left(l), right(r) {}
};

int evaluateNode(Node* node)
{
    if (node->token.type == TokenType::Number)
        return node->value;

    int leftValue = evaluateNode(node->left);
    int rightValue = evaluateNode(node->right);

    switch (node->op)
    {
        case '+': return leftValue + rightValue;
        case '-': return leftValue - rightValue;
        case '*': return leftValue * rightValue;
        case '/':
            assert(rightValue != 0); // Division by zero check
            return leftValue / rightValue;
        default:
            assert(false); // Invalid operator
    }
}


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

    char c;
    stack<Node*> nodes;
    stack<Token> operators;

    while (fin >> c)
    {
        switch (c)
        {
            case '(':
                operators.push(Token(c));
                break;
            case '*':
            case '/':
                while (!operators.empty() && (operators.top().op == '*' || operators.top().op == '/'))
                {
                    Node* right = nodes.top();
                    nodes.pop();
                    Node* left = nodes.top();
                    nodes.pop();
                    nodes.push(new Node(operators.top().op, left, right));
                    operators.pop();
                }
                operators.push(c);
                break;
            case '+':
            case '-':
                while (!operators.empty() && ((operators.top().type == TokenType::Operator) && operators.top().op != '('))
                {
                    Node* right = nodes.top();
                    nodes.pop();
                    Node* left = nodes.top();
                    nodes.pop();
                    nodes.push(new Node(operators.top().op, left, right));
                    operators.pop();
                }
                operators.push(c);
                break;
            case ')':
                while (!operators.empty() && operators.top().op != '(')
                {
                    Node* right = nodes.top();
                    nodes.pop();
                    Node* left = nodes.top();
                    nodes.pop();
                    nodes.push(new Node(operators.top().op, left, right));
                    operators.pop();
                }
                assert(!operators.empty());
                assert(operators.top().op == '(');

                if (!operators.empty()) operators.pop(); // Pop the '('
                break;
            default:
                assert(isdigit(c));
                string number;
                number += c;
                while (fin.peek() != EOF && isdigit(fin.peek()))
                {
                    fin >> c;
                    number += c;
                }
                nodes.push(new Node(stoi(number)));
        }
    }

    while (!operators.empty())
    {
        Node* right = nodes.top();
        nodes.pop();
        Node* left = nodes.top();
        nodes.pop();
        nodes.push(new Node(operators.top().op, left, right));
        operators.pop();
    }

    assert(!nodes.empty());

    Node* root = nodes.top();
    nodes.pop();

    fout << evaluateNode(root) << '\n';
    return 0;
}