Pagini recente » Cod sursa (job #1975801) | Cod sursa (job #3275415) | Cod sursa (job #91991) | Borderou de evaluare (job #2000711) | Cod sursa (job #3182288)
#include <iostream>
#include <string>
#include <fstream>
#include <stack>
#include <sstream>
int search_op_without_parantheses(const std::string& expression, int left, int right, char op1, char op2) {
int counter = 0;
for (int i = right; i >= left; i--) {
if (expression[i] == ')') {
counter++;
continue;
}
else if (expression[i] == '(') {
counter--;
continue;
}
if ((expression[i] == op1 || expression[i] == op2) && counter == 0) {
return i;
}
}
return -1;
}
int get_parantheses_expression_left(const std::string& expression, int left) {
int i = left;
for (i = left; expression[i] != ')' && i < expression.size(); i++) {}
if (i == expression.size()) return -1;
return i;
}
int get_parantheses_expression_right(const std::string& expression, int right) {
int i = right;
for (i = right; expression[i] != '(' && i >= 0; i--) {}
if (i == -1) return -1;
return i;
}
bool verify_if_number(const std::string& expression, int left, int right) {
if (expression[left] == '-') left++;
for (int i = left; i <= right; i++) {
if (!isalnum(expression[i])) return false;
}
return true;
}
int convert_to_number(const std::string& expression, int left, int right) {
int pos = 1;
int result = 0;
bool ok = false;
if (expression[left] == '-') {
ok = true;
left++;
}
for (int i = right; i >= left; i--, pos *= 10) {
result += (expression[i] - '0') * pos;
}
if (ok) result *= -1;
return result;
}
int algorithm_1(const std::string& expresion, int left, int right) {
if (verify_if_number(expresion, left, right)) return convert_to_number(expresion, left, right);
int result = 0;
int pos;
pos = search_op_without_parantheses(expresion, left, right, '+', '-');
if (pos == -1) pos = search_op_without_parantheses(expresion, left, right, '*', '/');
if (pos == -1) {
result += algorithm_1(expresion, left + 1, right - 1);
return result;
}
int number_left = algorithm_1(expresion, left, pos - 1);
int number_right = algorithm_1(expresion, pos + 1, right);
switch (expresion[pos]) {
case '+':
result += number_left + number_right;
break;
case '-':
result += number_left - number_right;
break;
case '*':
result += number_left * number_right;
break;
case '/':
result += number_left / number_right;
break;
}
return result;
}
int evaluate_expression(int number_1, int number_2, char op_code) {
switch (op_code) {
case '+':
return number_1 + number_2;
case '-':
return number_1 - number_2;
case '*':
return number_1 * number_2;
case '/':
return number_1 / number_2;
}
}
bool verify_op_code(char character) {
if (character == '+' || character == '-' || character == '*' || character == '/' || character == '(' || character == ')') return true;
return false;
}
int get_character_priority(char character) {
if (character == '-' || character == '+') return 1;
else if (character == '*' || character == '/') return 2;
else if (character == '(' || character == ')') return 0;
}
int get_number(const std::string& expression, int& i) {
std::stringstream buffer;
if (expression[i] == '-') {
buffer << '-';
i++;
}
for (;!verify_op_code(expression[i]) && i < expression.size(); i++) {
buffer << expression[i];
}
i--;
int number;
buffer >> number;
return number;
}
void evaluate_stacks(std::stack<char>& op_codes, std::stack<int>& numbers) {
char op_code = op_codes.top();
op_codes.pop();
int number2 = numbers.top();
numbers.pop();
int number1 = numbers.top();
numbers.pop();
int result = evaluate_expression(number1, number2, op_code);
numbers.push(result);
}
int algorithm_2(const std::string& expression) {
std::string buffer = "";
std::stack<char> op_codes;
std::stack<int> numbers;
bool is_number = true;
int parantheses_order = 0;
for (int i = 0; i < expression.size(); i++) {
if (expression[i] == '(') {
op_codes.push('(');
parantheses_order++;
continue;
}
else if (expression[i] == ')') {
parantheses_order--;
while (op_codes.top() != '(') {
evaluate_stacks(op_codes, numbers);
}
op_codes.pop();
continue;
}
std::cout << expression[i];
if (verify_op_code(expression[i])) {
char old_op_code = '(';
if (op_codes.size() >= 1) old_op_code = op_codes.top();
op_codes.push(expression[i]);
if (!(op_codes.size() >= 2) || get_character_priority(expression[i]) > get_character_priority(old_op_code)) continue;
char temp_buffer = op_codes.top();
op_codes.pop();
evaluate_stacks(op_codes, numbers);
op_codes.push(temp_buffer);
continue;
}
numbers.push(get_number(expression, i));
}
while (!op_codes.empty()) evaluate_stacks(op_codes, numbers);
return numbers.top();
}
int main()
{
std::ifstream fin("evaluare.in");
std::ofstream fout("evaluare.out");
std::string expression;
fin >> expression;
fout << algorithm_2(expression);
}