Pagini recente » Cod sursa (job #136267) | Cod sursa (job #239474) | Cod sursa (job #2546146) | Cod sursa (job #1094888) | Cod sursa (job #2969511)
#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;
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())){
// polishExpressionPush(polishExpression, polishExpressionLastIndex, operatorStack.top(), 1);
// operatorStack.pop();
// 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';
}