Pagini recente » Cod sursa (job #2797215) | Cod sursa (job #2898345) | Cod sursa (job #1278822) | Cod sursa (job #209889) | Cod sursa (job #941407)
Cod sursa(job #941407)
// evaluare Polish-expression and stack
#include <string>
#include <stack>
#include <vector>
#include <iostream>
#include <cstdio>
#include <fstream>
#include <cctype>
using namespace std;
typedef long long LL;
stack<char> operations;
stack<LL> factors;
bool is_oper(char c) {
return (c =='-') || (c == '+') || (c == '*') || (c == '/');
}
bool is_par(char c) {
return ((c == '(') || (c == ')'));
}
bool high_prec(char c, char d) {
if ((c == '*' || c == '/') && (d == '+' || d == '-')) return true;
return false;
}
string process_line(string &line) {
operations.push('!');
string ret;
int i = 0;
int s = line.size();
//operations.clear();
while(i < s){
//cout << i << endl;
char c = line[i];
//cout << c << endl;
if (isdigit(c)) if(i > 0 && !isdigit(line[i-1])) {ret += ' '; ret += c; i++;}
else {ret += c; i++;}
else if (is_par(c)) {if (c == '(') {operations.push(c); i++;}
else {c = operations.top();
while (c != '(') {
ret += c;
operations.pop();
c = operations.top();
}
operations.pop();
i++;
}
}
else {char d = operations.top();
while(d != '!' && d != '(' && !high_prec(c,d)) {
ret += d; operations.pop(); d = operations.top();
}
operations.push(c); i++;
}
//cout << ret << " : " << operations.top() << endl;
}
while(operations.top() != '!') {
char c = operations.top(); if (c != ')') ret += c;
operations.pop();
}
return ret;
}
LL eval_str(string &A)
{
LL ret = 0;
int i = 0;
int s = A.size();
while(i < s) {
char c = A[i];
if (c == ' ') {
LL n = 0; i++; c = A[i];
while(isdigit(c)) {n *= 10; n += c - '0'; i++; c = A[i];}
factors.push(n);
}
else if (is_oper(c)) {
LL n = factors.top(); factors.pop(); LL m = factors.top(); factors.pop();
if (c == '+') m += n;
else if (c == '-') m -= n;
else if (c == '*') m *= n;
else if (c == '/') m /= n;
factors.push(m);
i++;
}
}
ret = factors.top();
return ret;
}
int main()
{
string line;
LL n;
ifstream fin ("evaluare.in");
ofstream fout("evaluare.out");
getline(fin, line);
string RPN = process_line(line);
LL result = eval_str(RPN);
fout << result << endl;
return 0;
}