Cod sursa(job #2969457)

Utilizator Redstoneboss2Fabian Lucian Redstoneboss2 Data 23 ianuarie 2023 02:12:29
Problema Evaluarea unei expresii Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 4.56 kb
#include <bits/stdc++.h>

using namespace std;

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

struct polishExpressionElement {
    long long val;
    bool isOperator;
};

long long evaluate(string expression);
void convert(string expression, vector<polishExpressionElement>& polishExpression, int& polishExpressionLastIndex);
void polishExpressionPush(vector<polishExpressionElement>& polishExpression, int& polishExpressionLastIndex, long long val, bool isOperator);
int priority(char operator_);
bool isNum(char chr);

int main(){

    string expression;

    //cout << "Enter expression:\n\n";

    getline(fin, expression);

    fout << evaluate(expression);

    return 0;
}

long long evaluate(string expression){
    stack<long long> operandStack;
    vector<polishExpressionElement> polishExpression(expression.size());
    int polishExpressionLastIndex = -1;

    convert(expression, polishExpression, polishExpressionLastIndex);

    for(int i = 0; i <= polishExpressionLastIndex; i++){
        if(polishExpression[i].isOperator){
            long long num1, num2, result;
            num2 = operandStack.top();
            operandStack.pop();
            num1 = operandStack.top();
            operandStack.pop();

            switch(polishExpression[i].val){
                case '+':
                    result = num1 + num2;
                    break;
                case '-':
                    result = num1 - num2;
                    break;
                case '*':
                    result = num1 * num2;
                    break;
                case '/':
                    result = num1 / num2;
                    break;
            }

            operandStack.push(result);
        }else{
            operandStack.push(polishExpression[i].val);
        }
    }

    return operandStack.top();
}

void convert(string expression, vector<polishExpressionElement>& polishExpression, int& polishExpressionLastIndex){
    stack<char> operatorStack;

    // 1 + 21*3 + (1+1)*13

    for(int i = 0; i < expression.size(); i++){
        if(expression[i] == ' '){
            continue;
        }else if(isNum(expression[i])){
            long long currentNumber = 0;
            
            while(i < expression.size() && isNum(expression[i])){
                currentNumber = currentNumber*10 + expression[i] - '0';
                i++;
            }

            i--;

            polishExpressionPush(polishExpression, polishExpressionLastIndex, currentNumber, 0);
        }else if(expression[i] == '('){
            operatorStack.push('(');
        }else if(expression[i] == ')'){
            while(operatorStack.top() != '('){
                polishExpressionPush(polishExpression, polishExpressionLastIndex, operatorStack.top(), 1);
                operatorStack.pop();
            }

            operatorStack.pop();
        }else if(operatorStack.empty() || priority(expression[i]) >= priority(operatorStack.top())){
            operatorStack.push(expression[i]);
        }else if(!operatorStack.empty() && priority(expression[i]) < priority(operatorStack.top())){
            while(!operatorStack.empty() && priority(expression[i]) < priority(operatorStack.top())){
                polishExpressionPush(polishExpression, polishExpressionLastIndex, operatorStack.top(), 1);
                operatorStack.pop();
            }

            operatorStack.push(expression[i]);
        }
    }

    while(!operatorStack.empty()){
        polishExpressionPush(polishExpression, polishExpressionLastIndex, operatorStack.top(), 1);
        operatorStack.pop();
    }

    // for(int i = 0; i <= polishExpressionLastIndex; i++){
    //     if(polishExpression[i].isOperator){
    //         cout << (char)polishExpression[i].val << ' '; 
    //     }else{
    //         cout << polishExpression[i].val << ' ';
    //     }
    // }

    // cout << '\n';
}

void polishExpressionPush(vector<polishExpressionElement>& polishExpression, int& polishExpressionLastIndex, long long val, bool isOperator){
    polishExpressionLastIndex++;
    polishExpression[polishExpressionLastIndex].val = val;
    polishExpression[polishExpressionLastIndex].isOperator = isOperator;
}

int priority(char operator_){
    switch(operator_){
        case '(':
            return 0;
        case '+':
        case '-':
            return 1;
        case '*':
        case '/':
            return 2;
        default:
            return 0;
    }
}

bool isNum(char chr){
    return '0' <= chr && chr <= '9';
}