#include <fstream>
#include <iostream>
#include <stack>
#include <unordered_set>
#include <vector>
using namespace std;
ifstream fin("evaluare.in");
ofstream fout("evaluare.out");
static constexpr char OPEN_PARENTHESIS = '(';
static constexpr char CLOSED_PARENTHESIS = ')';
enum OPERATORS {
MULTIPLY = '*',
DIVIDE = '/',
ADD = '+',
SUBTRACT = '-'
};
enum PostfixElementType {
NUMBER_TYPE,
OPERATOR_TYPE
};
struct PostfixElement {
PostfixElementType elementType;
int value;
};
struct PostfixNotation {
vector<PostfixElement> elements;
};
static const unordered_set<char> OPERATORS_SET{ MULTIPLY, DIVIDE, ADD, SUBTRACT };
inline int evaluateOperator(char operatorValue, int firstOperand, int secondOperand) {
switch (operatorValue) {
case MULTIPLY:
return firstOperand * secondOperand;
case DIVIDE:
return firstOperand / secondOperand;
case ADD:
return firstOperand + secondOperand;
default:
return firstOperand - secondOperand;
}
}
void evaluateTopOperation(stack<int>& numbers, char operatorValue) {
int secondOperand = numbers.top();
numbers.pop();
int firstOperand = numbers.top();
numbers.pop();
numbers.push(evaluateOperator(operatorValue, firstOperand, secondOperand));
}
// Higher value means a higher precedence (evaluated before those with lower precedence)
inline int getPrecedence(char operatorValue) {
if (operatorValue == MULTIPLY || operatorValue == DIVIDE) {
return 2;
} else if (operatorValue == ADD || operatorValue == SUBTRACT) {
return 1;
}
return 0;
}
void actOnOperator(char operatorValue, stack<char>& operators, PostfixNotation& postfixNotation) {
while (!operators.empty() && getPrecedence(operators.top()) >= getPrecedence(operatorValue)) {
postfixNotation.elements.push_back(PostfixElement{OPERATOR_TYPE, operators.top()});
operators.pop();
}
operators.push(operatorValue);
}
inline bool isDigit(char character) {
return '0' <= character && character <= '9';
}
int parseNumber(const string& expression, int firstDigitIndex) {
int number = 0;
for (int currentIndex = firstDigitIndex; currentIndex < (int)expression.size() && isDigit(expression[currentIndex]); currentIndex++) {
number = number * 10 + (expression[currentIndex] - '0');
}
return number;
}
// Returns the index of the last character forming the number plus one.
int actOnNumber(const string& expression, int firstDigitIndex, stack<char>& operators, PostfixNotation& postfixNotation) {
int number = parseNumber(expression, firstDigitIndex);
postfixNotation.elements.push_back(PostfixElement{NUMBER_TYPE, number});
int lastDigitIndex = firstDigitIndex;
while (lastDigitIndex + 1 < (int)expression.size() && isDigit(expression[lastDigitIndex + 1])) {
lastDigitIndex++;
}
return lastDigitIndex + 1;
}
PostfixNotation getPostfixNotation(const string& expression) {
stack<char> operators;
PostfixNotation postfixNotation;
int currentIndex = 0;
while (currentIndex < (int)expression.size()) {
if (OPERATORS_SET.find(expression[currentIndex]) != OPERATORS_SET.end()) {
actOnOperator(expression[currentIndex], operators, postfixNotation);
currentIndex++;
} else if (expression[currentIndex] == OPEN_PARENTHESIS) {
operators.push(OPEN_PARENTHESIS);
currentIndex++;
} else if (expression[currentIndex] == CLOSED_PARENTHESIS) {
while (operators.top() != OPEN_PARENTHESIS) {
postfixNotation.elements.push_back(PostfixElement{OPERATOR_TYPE, operators.top()});
operators.pop();
}
operators.pop();
currentIndex++;
} else {
currentIndex = actOnNumber(expression, currentIndex, operators, postfixNotation);
}
}
while (!operators.empty()) {
postfixNotation.elements.push_back(PostfixElement{OPERATOR_TYPE, operators.top()});
operators.pop();
}
return postfixNotation;
}
int evaluatePostfixExpression(PostfixNotation& postfixExpression) {
stack<int> numbers;
for (const auto& element : postfixExpression.elements) {
if (element.elementType == NUMBER_TYPE) {
numbers.push(element.value);
} else {
evaluateTopOperation(numbers, element.value);
}
}
return numbers.top();
}
int main() {
string expression;
getline(fin, expression);
PostfixNotation postfixNotation = getPostfixNotation(expression);
// for (auto& element : postfixNotation.elements) {
// if (element.elementType == NUMBER_TYPE) {
// cout << element.value << " ";
// } else {
// cout << (char)element.value << " ";
// }
// }
fout << evaluatePostfixExpression(postfixNotation);
return 0;
}