327 - Evaluating Simple C Expressions

[Sakib]

are this inputs possible ???????

++a + ++b + ++c
or
a++ + b++ + c++
please give the correct output.

i m getting WAAAA!!!!!!!
i think no var will be used more than once (according to the problem description).

please give me some other test cases.

Thanks.

[guma]

Here's some sample input and my programs (which is AC) output. Maybe it can help?

b++---c+d-c+b

should yield

Expression: b++---c+d-c+b
value = 5
b = 3
c = 2
d = 4

I get value = 4 and my program was AC

From the problem's description:

Each variable will appear at most once in an expression, and many variables may not be used at all.

So, the sample I/O posted by Yarin isn't valid.
For example, my AC program Output this:

Expression: b++---c+d-c+b
value = 3
b = 3
b = 2
c = 2
c = 3
d = 4

[fh]

There is a missing steps that weren't mentioned in the problem statement: Remove Spaces before running the algorithm!

When I add this preprocessing, I got AC:

Code: Select all

gets(line); // this is the expression

for (int i=0,j=0; line[j]; j++){
    if (!isspace(line[j])) line[i++] = line[j];
    if (line[j+1]=='\0') line[i] = '\0';
}

So it is possible to have a unary operator and the variable separated with space like a ++, beware.

[awais]

Hi,
I spent ages to correctly submit my solution but failed... though I can compute all the available sample inputs. Could anybody help... Thanks for reading my post.

Regards,
Awais

/* @JUDGE_ID: AWAIS 327 C++ "Dynamic Programming" */
#include <iostream>
#include <cstdlib>
#include <string>
#include <stack>
#include <list>
#include <fstream>

using namespace std;
//type 1: alpha
//type 2: binary-operator
//type 3: uni-operator


class Term{
public:
string d;
int type;
int defaultValue;
int newValue;

Term()
{
d = "";
type = 1; // By default type is alpha
newValue = defaultValue = 0;
}

Term(string s)
{
d = s;

type = 1; // By default type is alpha
if(d.compare("++") == 0 || d.compare("--") == 0)
type = 3;
else if(d.compare("+") == 0 || d.compare("-") == 0)
type = 2;
else
newValue = defaultValue = d[0]-96;
}

int get_type()
{
return type;
}
};

class leaf
{
public:
leaf* left;
leaf* right;
Term* t;

leaf()
{
left = right = NULL;
t = NULL;
}

leaf(Term* d)
{
left = right = NULL;
t = new Term(d->d);
}
/*
int evaluate()
{
int result = 0;
if(t->type == 1)
result = t->d[0]-96;
else if(t->type == 3){
if(left != NULL){
result = left->evaluate();
if(t->d.compare("++") == 0)
result++;
else
result--;
}
}
else{
int r = right->evaluate();
int l = left->evaluate();
if(t->d.compare("+") == 0)
result = l + r;
else
result = l - r;
if(result < 0) result *= -1; // Remove -1 sign
}
return result;
}
*/

int evaluate(leaf* p, list<leaf>* que)
{
int result = 0;
if(t->type == 1){

bool isNeighbourUniOp = false;
bool isNeighbourUniOpDecriment = false;

if(p != NULL)
if(p->t->get_type() == 3){
isNeighbourUniOp = true;
if(p->t->d.compare("--") == 0) isNeighbourUniOpDecriment = true;
}
if(!isNeighbourUniOp)
{
if(this->left != NULL){
if(this->left->t->get_type() == 3){
isNeighbourUniOp = true;
if(this->left->t->d.compare("--") == 0) isNeighbourUniOpDecriment = true;
}
}
}
if(isNeighbourUniOp)
{
if(isNeighbourUniOpDecriment)
t->newValue = t->defaultValue - 1;
else
t->newValue = t->defaultValue + 1;
}

result = t->defaultValue;
que->push_back(*this);
}else if(t->type == 3){
if(left != NULL){
result = left->evaluate(this, que);
if(t->d.compare("++") == 0)
result++;
else
result--;
}
}
else{
int r = 0;
if(right != NULL)
r = right->evaluate(this, que);

int l = 0;
if (left != NULL)
l =left->evaluate(this, que);
if(t->d.compare("+") == 0)
result = r + l;
else
result = r - l;
//if(result < 0) result *= -1; // Remove '-' sign
}
return result;
}
};

int cmp(const leaf & a, const leaf & b)
{
return a.t->d < b.t->d;
}

class ExprTree
{
private:
leaf* root;
public:
ExprTree(){
root = NULL;
}

bool isEmpty() const { return root == NULL; }

void Insert(stack<Term>* s){
leaf* lbol = NULL; //last binary operator node
leaf* l = NULL;

if(root == NULL){
root = new leaf(&s->top());
s->pop();

lbol = GetLastOperatorLeaf(root);
if(!s->empty()){
l = new leaf(&s->top());
s->pop();
if(lbol != NULL)
lbol->left = l;
else
root->left = l;
}
}else{
lbol = GetLastOperatorLeaf(root);
l = new leaf(&s->top());
s->pop();

if(lbol != NULL)
{
lbol->right = l;
}
}

while(!s->empty())
{
l->left = new leaf(&s->top());
s->pop();
l = l->left;
}
}

leaf* GetLastOperatorLeaf(leaf* t){
if(t == NULL) return NULL;
if(t->t->type == 2 && t->right == NULL)
return t;
else
return GetLastOperatorLeaf(t->right);
}

void ReverseInOrder()
{
ReverseInOrder(root);
}

void ReverseInOrder(leaf* p)
{
if(p != NULL)
{
if(p->right)
ReverseInOrder(p->right);
cout<<p->t->d<<" ";
if(p->left)
ReverseInOrder(p->left);
}
else return;
}

int Evaluate(list<leaf>* que)
{
int result = 0;
if(root != NULL)
result = root->evaluate(NULL, que);
return result;
}
};

class Token{
int curr;
string express;
Term* lastTerm;
string oldexpress;
public:
string get_oldexpress()
{
return oldexpress;
}

int size()
{
return express.length();
}

Token(string ex)
{
oldexpress = ex;
removeAllWhite(ex);
express = ex;
curr = size();
lastTerm = NULL;
}

void removeAllWhite (std::string &str)
{
std::string temp;
for (unsigned int i = 0; i < str.length(); i++)
if (str != ' ') temp += str;
str = temp;
}

Term* getNextToken()
{
bool isLastTermUniOperator = false;
if(lastTerm != NULL)
if(lastTerm->get_type() == 3)
isLastTermUniOperator = true;

curr--;
std::string temp;
temp = express[curr];
if(curr > 0){
if(!isLastTermUniOperator)
if(temp[0] == express[curr-1])
{
/*if((curr-2) > 0){
if(temp[0] != express[curr-2])
{
temp += express[curr-1];
curr--;
}
}
else
{*/
temp += express[curr-1];
curr--;
//}
}
}
lastTerm = new Term(temp);
return lastTerm;
}

void reset()
{
curr = size();
lastTerm = NULL;
}
bool EOE()
{
if(curr != 0)
return false;
else
return true;
}
};

void ComputeExpression(string exp)
{
ExprTree tree;
Token token(exp);
//Token token("a+++++b");
int i = 0;
stack<Term> stack;
while(!token.EOE())
{
Term* t = token.getNextToken();
stack.push(*t);
if(stack.top().d == "+" || stack.top().d == "-" || token.EOE())
{
if(!stack.empty())
tree.Insert(&stack);
}
}
cout<<"Expression: "<<token.get_oldexpress();
//cout<<" ***[";
//tree.ReverseInOrder();
//cout<<"]*** ";
//;

list<leaf>* vec = new list<leaf>();
cout<<endl<<"\tvalue = "<<tree.Evaluate(vec)<<endl;

vec->sort(cmp);

while(!vec->empty()){
cout<<"\t"<<vec->front().t->d<<" = "<<vec->front().t->newValue<<endl;
vec->pop_front();
}
}

int main()
{
std::string sLine;

#ifndef ONLINE_JUDGE
std::ifstream inFile("327.txt");
while(std::getline(inFile, sLine))
{
ComputeExpression(sLine);
}
#endif

return 0;
}

[casinoenligne]

I agree with you guys.