Pagini recente » Cod sursa (job #3208125) | Cod sursa (job #1700043) | Cod sursa (job #3136052) | Cod sursa (job #1334955) | Cod sursa (job #2233360)
#include <fstream>
#include <iostream>
#include <stack>
#include <ctype.h>
#include <map>
using namespace std;
class cTree
{
private:
int m_value;
cTree* m_left;
cTree* m_right;
bool m_isLeaf;
public:
cTree(int value, cTree* left, cTree* right, bool isLeaf);
~cTree(){}
int getValue() { return m_value; }
cTree* getLeft() { return m_left; }
cTree* getRight() { return m_right; }
bool isLeaf() { return m_isLeaf; }
};
cTree::cTree(int value, cTree* left, cTree* right, bool isLeaf)
:m_value(value), m_left(left), m_right(right), m_isLeaf(isLeaf){}
class cExpressionTree
{
private:
cTree* tree;
public:
cExpressionTree(std::string expression);
~cExpressionTree();
cTree* getTree() { return tree; }
int getExpressionValue();
private:
cTree* generateTree(std::string expression);
int priority(char c);
int inorderValues(cTree* node);
};
cExpressionTree::cExpressionTree(std::string expression)
{
tree = generateTree(expression);
}
int cExpressionTree::priority(char c) {
if(c == '*' || c == '/')
return 2;
if(c =='+' || c == '-')
return 1;
return 0;
}
cTree* cExpressionTree::generateTree(std::string expression)
{
expression = "(" + expression + ")";
std::stack<char> operatorStack;
std::stack<cTree*> operandStack;
int ident = -1;
int counter = 0;
for(std::string::iterator ii = expression.begin(); ii != expression.end(); ++ii) {
int size = 0;
char c = *ii;
if(isdigit(c)) {
if(ident == -1)
ident = 0;
ident = ident * 10 + (c - '0') ;
}
else {
if(ident >= 0)
operandStack.push(new cTree(ident, nullptr, nullptr, true));
size = operandStack.size();
ident = -1;
if(c == '/' || c =='*' || c == ')' || c == '-' || c == '+') {
char ceva = operatorStack.top();
int priorityc = priority(c);
int priorityceva = priority(ceva);
while(!operatorStack.empty() && priority(c) <= priority(operatorStack.top())) {
char top = operatorStack.top();
operatorStack.pop();
if(top != '(') {
cTree* right = operandStack.top();
operandStack.pop();
cTree* left = operandStack.top();
operandStack.pop();
operandStack.push(new cTree((int)top, left, right, false));
}
else
break;
}
if(c != ')') {
operatorStack.push(c);
}
}
else
if(c == '(') {
operatorStack.push(c);
}
}
}
cTree *res = operandStack.top();
operandStack.pop();
if(operandStack.size()>0)
cout << operandStack.size() << endl;
return res;
}
int cExpressionTree::getExpressionValue() {
return inorderValues(tree);
}
int cExpressionTree::inorderValues(cTree* node) {
if(node->isLeaf()) {
return node->getValue();
}
if(node->getValue() == '+') {
return inorderValues(node->getLeft()) + inorderValues(node->getRight());
}
if(node->getValue() == '-') {
return inorderValues(node->getLeft()) - inorderValues(node->getRight());
}
if(node->getValue() == '*') {
return inorderValues(node->getLeft()) * inorderValues(node->getRight());
}
return inorderValues(node->getLeft()) / inorderValues(node->getRight());
}
void inorder(cTree* tree) {
if(tree == nullptr)
return;
inorder(tree->getLeft());
inorder(tree->getRight());
if(tree->isLeaf())
cout << tree->getValue() << " ";
else
cout << (char)(tree->getValue()) << " ";
}
int main()
{
ifstream fin("evaluare.in");
ofstream fout("evaluare.out");
string value;
fin >> value;
cExpressionTree* tree = new cExpressionTree(value);
inorder(tree->getTree());
fout << tree->getExpressionValue();
return 0;
}