11416 - Excel Evaluation

[kantaki]

This code pass the sample input.
but I've got WA.
What is my problem? Please help me

Code: Select all

#include <stdio.h>
#define MAX 30000
#define EMAX 50
#define MAX_STACK_SIZE 100
#define MAX_EXPR_SIZE 100

typedef struct {
	int mine_row;
	int mine_col;
	char expr[MAX_EXPR_SIZE];
} Eval;
Eval e[MAX];

int excel[1001][20000];
int evaled[1001][20000];
char lines[256];
int data[EMAX];

typedef enum {lparen, rparen, plus, minus, times, divide, mod, eos, operand} precedence;
static int isp[] = {0, 19, 12, 12, 13, 13, 13, 0};
static int icp[] = {20, 19, 12, 12, 13, 13, 13, 0};

int stack[MAX_STACK_SIZE];
char expr[MAX_EXPR_SIZE];

void  add(int *top, precedence item);
precedence delete(int *top);
void  stack_full();
precedence stack_empty();
precedence get_token(char *r_expr, char *symbol, int *n);
char  print_token(precedence token);
char* postfix(char * r_expr);
int eval(char *r_expr);


void add(int *top, precedence item)
{
	if(*top >= MAX_STACK_SIZE -1)
	{
		stack_full();
		return;
	}
	stack[++*top] = item;
}

precedence delete(int *top)
{
	if(*top == -1)
		return stack_empty(); 
	return stack[(*top)--];
}

void stack_full()
{
}

precedence stack_empty()
{
	return operand;
}

precedence get_token(char *r_expr, char *symbol, int *n)
{
	int i;
	i=0;
	symbol[i++] = r_expr[(*n)++];

	switch(symbol[0])
	{
	case '(' : return lparen;
	case ')' : return rparen;
	case '+' : return plus;
	case '-' : return minus;
	case '/' : return divide;
	case '*' : return times;
	case '%' : return mod;
	case '\0' : return eos; 
	default  : 
		while(r_expr[(*n)] != '(' &&r_expr[(*n)] != ')' &&r_expr[(*n)] != '+' &&r_expr[(*n)] != '-' &&
			r_expr[(*n)] != '*' &&r_expr[(*n)] != '/' &&r_expr[(*n)] != '%' &&r_expr[(*n)] != '\0')
			symbol[i++] = r_expr[(*n)++];
		symbol[i] = 0;

		return operand; 
	}
}

char print_token(precedence token)
{
	
	switch( token )
	{
	case lparen: break;
	case rparen: break;
	case plus:  return '+';
	case minus:  return '-';
	case divide: return '/';
	case times:  return '*';
	case mod:  return '%';
	case eos:  return '\0';
	case operand: break; 
	}

	return ' ';
}


char rpostfix[MAX_EXPR_SIZE]; 

char* postfix(char * r_expr)
{
	
	int rn = 0; 
	char symbol[10];
	precedence token;
	int n = 0;
	int top = 0; 
	int length;
	int i;

	stack[0] = eos;

	for(token = get_token(r_expr, symbol, &n); token != eos; token = get_token(r_expr, symbol, &n))
	{
		if(token == operand) {
			length = strlen(symbol);
			for(i=0;i<length;i++)
				rpostfix[rn++] = symbol[i];
		}
		else if(token == rparen) 
		{
			while (stack[top] != lparen)
				rpostfix[rn++] = print_token(delete(&top));
			delete(&top); 
		}else
		{
			while(isp[stack[top]] >= icp[token])
				rpostfix[rn++] = print_token(delete(&top));
			add(&top, token);
		}
	}

	while((token = delete(&top)) != eos)
		rpostfix[rn++] = print_token(token);
	rpostfix[rn] = '\0';
	
	return rpostfix;

}



int eval(char *r_expr)
{
	precedence token;
	char symbol;
	int op1, op2;
	int n = 0; 
	int top = -1;
	token = get_token(r_expr, &symbol, &n);
	while(token != eos)
	{
		if(token == operand)
			add(&top, symbol - '0'); 
		else 
		{
			op2 = delete(&top); 
			op1 = delete(&top);
			switch(token)
			{
			case plus:  add(&top, op1 + op2);  break;
			case minus:  add(&top, op1 - op2);  break;
			case times:  add(&top, op1 * op2);  break;
			case divide: add(&top, op1 / op2);  break;
			case mod:  add(&top, op1 % op2);  break;
			}
		}
		token = get_token(r_expr, &symbol, &n);
	}
	return delete(&top); 
}


char calcexpr[MAX_EXPR_SIZE];
int resss;

int GetData(int pos) {
	int t_col, t_row;
	int length;
	int flag;
	int k, i;
	int wpos;
	int t_length;
	precedence token;
	char symbol;
	int op1, op2;
	int n = 0; 
	int top = -1;

	length = strlen(e[pos].expr);
	wpos = 0;
	
	
	for(k=0;k<length;) {
		t_col = t_row = 0;
		while(e[pos].expr[k] >= 'A' && e[pos].expr[k] <= 'Z') {
			t_col=t_col*26+e[pos].expr[k]-'A'+1;
			k++;
		}
		while(e[pos].expr[k] >= '0' && e[pos].expr[k] <= '9') {
			t_row=t_row*10+e[pos].expr[k]-'0';
			k++;
		}
		if(!evaled[t_row][t_col]) return 0;

		


		add(&top, excel[t_row][t_col]); 

		
		while(e[pos].expr[k] == '*' || e[pos].expr[k] == '/' || e[pos].expr[k] == '+' || e[pos].expr[k] == '-') {

			op2 = delete(&top); 
			op1 = delete(&top);
			switch(e[pos].expr[k++])
			{
			case '+':  add(&top, op1 + op2);  break;
			case '-':  add(&top, op1 - op2);  break;
			case '*':  add(&top, op1 * op2);  break;
			case '/': add(&top, op1 / op2);  break;
			}

		}
	}
	resss=delete(&top);
	return 1;
}

int main ()
{
	int rep;
	int row, col;
	int i, j, k;
	int length;
	int d_length;
	int data_pos;
	int eval_count;
	int flag;
	int count;

	scanf("%d", &rep);
	while(rep--) {
		scanf("%d %d", &row, &col);
		eval_count = 0;
		for(i=0;i<=row;i++)
			for(j=0;j<=col;j++) evaled[i][j] = 0;

		for(i=1;i<=row;i++) {
			for(j=1;j<=col;j++) {
				scanf("%s", lines);
				if(lines[0] != 'e') {
					excel[i][j] = atoi(lines);
					evaled[i][j] = 1;
				}
				else {
					length = strlen(lines);
					e[eval_count].mine_row = i;
					e[eval_count].mine_col = j;
					strcpy(e[eval_count++].expr, postfix(&lines[1]));
				}
			}
		}
		i=0;
		count = 0;

		while(eval_count != count) {
			flag = 1;
			if(evaled[e[i].mine_row][e[i].mine_col]) 
				flag = 0;
			if(GetData(i)) {
				evaled[e[i].mine_row][e[i].mine_col] = 1;
				excel[e[i].mine_row][e[i].mine_col] = resss;
				count++;

			}
			i=(i+1)%eval_count;
		}

		for(i=1;i<=row;i++) {
			printf("%d", excel[i][1]);
			for(j=2;j<=col;j++) {
				printf(" %d", excel[i][j]);
			}
			printf("\n");
		}
		printf("\n");
	}
	return 0;
}

[d8888]

Code: Select all

#include <stdio.h>
#include <list>
#include <string>
#include<vector>
using namespace std;

const int MAXROW=1024;
const int MAXCOL=18000;

enum otype{oadd,ominus,otime,odivide,lpar,rpar};
class bignum
{
protected:
	vector<int> val; 
	void delzero();
	void setval(vector<int>& target);
public:
	bignum();
	bignum(string);
	bignum(int);
	bignum& operator=(const bignum &target);
	bignum operator+(const bignum &target)const;
	bignum operator-(const bignum &target)const;
	bool operator>(const bignum &target) const;
	bool operator==(const bignum &target) const;
	bignum operator*(const bignum &target)const;
	bignum operator/(const bignum &target)const;
	virtual string output(void);
};


class signedbignum:public bignum
{
private:
	bool ispositive;
	string absstr(string);
public:
	signedbignum();
	signedbignum(string val):bignum(absstr(val))
	{
		ispositive=true;
		if(val[0]=='-')
		{
			ispositive=false;
		}
	}
	signedbignum(int val):bignum(val<0?-val:val)
	{
		ispositive=val>0;
	}
	signedbignum(const bignum&);
	signedbignum operator+(const signedbignum&);
	signedbignum operator-(const signedbignum&);
	signedbignum operator*(const signedbignum&);
	signedbignum operator/(const signedbignum&);
	signedbignum& operator=(const signedbignum&);
	signedbignum& operator=(const bignum&);
	signedbignum operator>(const signedbignum&);
	string output(void);
};
string signedbignum::output(void)
{
	string rt;
	if(!this->ispositive && !(this->val.size()==1 && this->val[0]==0))
	{
		rt+='-';
	}
	rt+=bignum::output();
	return rt;
}
signedbignum::signedbignum():bignum()
{
	this->ispositive=true;
}
signedbignum::signedbignum(const bignum& target):bignum(target)
{
	this->ispositive=true;
}
signedbignum& signedbignum::operator=(const bignum& target)
{
	this->bignum::operator=(target);
	this->ispositive=true; //bignum class is always positive
	return *this;
}
signedbignum& signedbignum::operator=(const signedbignum& target)
{
	this->ispositive=target.ispositive;
	this->bignum::operator=(target);
	return *this;
}
signedbignum signedbignum::operator>(const signedbignum& target)
{
	if(this->ispositive)
	{
		if(target.ispositive)
		{
			return this->bignum::operator>(target);
		}else
		{
			return true;
		}
	}else
	{
		if(target.ispositive)
		{
			return true;
		}else
		{
			return !this->bignum::operator>(target);
		}
	}
}
signedbignum signedbignum::operator+(const signedbignum& target)
{
	signedbignum rt;
	if(this->ispositive)
	{
		if(target.ispositive)
		{
			rt=this->bignum::operator+(target);
			rt.ispositive=true;
		}else
		{
			rt=this->bignum::operator-(target);
			if(this->bignum::operator>(target))
			{
				rt.ispositive=true;
			}else
			{
				rt.ispositive=false;
			}
		}
	}else
	{
		if(target.ispositive)
		{
			rt=this->bignum::operator-(target);
			if(this->bignum::operator>(target))
			{
				rt.ispositive=false;
			}else
			{
				rt.ispositive=true;
			}
		}else
		{
			rt=this->bignum::operator+(target);
			rt.ispositive=false;
		}
	}
	return rt;
}

signedbignum signedbignum::operator-(const signedbignum& target)
{
	signedbignum temp=target;
	temp.ispositive=!temp.ispositive;
	return (*this)+temp;
}

signedbignum signedbignum::operator*(const signedbignum& target)
{
	signedbignum rt=this->bignum::operator*(target);
	rt.ispositive=(this->ispositive==target.ispositive);
	return rt;
}
signedbignum signedbignum::operator/(const signedbignum& target)
{
	signedbignum rt=this->bignum::operator/(target);
	rt.ispositive=(this->ispositive==target.ispositive);
	return rt;
}

string signedbignum::absstr(string val)
{
	if(val[0]=='-')
	{
		return val.substr(1);
	}
	return val;
}

string bignum::output(void)
{
	string rst;
	typedef vector<int>::iterator ii;
	for(ii i=val.end();i!=val.begin();i--)
	{
		rst+=(*(i-1)+'0');
	}
	return rst;
}


bignum::bignum()
{
	val.clear();
	val.push_back(0);
}

bignum::bignum(int aray)
{
	if(aray<0)
	{
		aray=-aray;
	}
	val.clear();
	do{
		val.push_back(aray%10);
		aray/=10;
	}while(aray>0);
}

bignum::bignum(string aray)
{
	val.clear();
	for(int i=aray.length()-1;i>=0;i--)
	{
		val.push_back(aray[i]-'0');
	}
}

void bignum::setval(vector<int>& target)
{
	this->val=target;
	delzero();
}

void bignum::delzero()
{
	while(val.back()==0&&val.size()>1)
	{
		val.pop_back();
	}
}
bignum& bignum::operator=(const bignum& target)
{
	if(this==&target)  //self assignment
	{
			return *this;
	}
	this->val=target.val;
	return *this;
}

bignum bignum::operator+(const bignum& target) const
{
	vector<int> rst;
	rst.clear();

	int len=(this->val.size()>target.val.size())?this->val.size():target.val.size();
	int carry=0;
	for(int i=0;i<len;i++)
	{
		int a=0;
		int b=0;
		rst.push_back(0);
		if(i<this->val.size())
		{
			a=this->val[i];
		}
		if(i<target.val.size())
		{
			b=target.val[i];
		}
		rst[rst.size()-1]=(a+b+carry)%10;
		carry=(a+b+carry)/10;
	}
	if(carry>0)
	{
		rst.push_back(carry);
	}
	if(rst.size()==0)
	{
		rst.push_back(0);
	}
	bignum rt;
	rt.setval(rst);
	return rt;
}

bignum bignum::operator-(const bignum &target) const
{
	const bignum *a,*b;
	if(target>(*this))
	{
		a=&target;
		b=this;
	}else
	{
		a=this;
		b=&target;
	}

	int len=a->val.size();
	vector<int> rst;
	rst.clear();
	for(int i=0,borrow=0;i<len;i++)
	{
		int x=a->val[i];
		int y=0;
		if(i<b->val.size())
		{
			y=b->val[i];
		}
		int r=x-y-borrow;
		if(r<0)
		{
			for(borrow=0;r<0;borrow++)
			{
				r+=10;
			}
		}else
		{
			borrow=0;
		}
		rst.push_back(r);
	}
	if(rst.size()==0)
	{
		rst.push_back(0);
	}
	bignum rt;
	rt.setval(rst);
	return rt;
}
bignum bignum::operator*(const bignum& target) const
{
	int lena=this->val.size();
	int lenb=target.val.size();
	vector<int> rst;
	rst.resize(lenb+lenb+1,0);
	for(int i=0;i<lena;i++)
	{
		for(int j=0;j<lenb;j++)
		{
			rst[i+j]+=this->val[i]*target.val[j];
			int now=i+j;
			while(rst[now]>=10)
			{
				rst[now+1]+=rst[now]/10;
				rst[now]%=10;
			}
		}
	}
	bignum rt;
	rt.setval(rst);
	return rt;
}
bignum bignum::operator/(const bignum& target) const
{
	int lena=this->val.size();
	int lenb=target.val.size();
	bignum rt=0;
	bignum temp=0;
	for(int i=lena-1;i>=0;i--)
	{
		temp=temp*10;
		temp=temp+this->val[i];
		int j=0;


		for(j=0;j<=10&&(temp>target*j|| temp==target*j);j++)
		{
		}
		j--;
		rt=rt*10;
		rt=rt+j;
		temp=temp - (target*j);
		
	}
	return rt;
}
bool bignum::operator>(const bignum& target) const
{
	if(this->val.size()>target.val.size())
	{
		return true;
	}
	if(this->val.size()<target.val.size())
	{
		return false;
	}
	int len=this->val.size();

	for(int i=len-1;i>=0;i--)
	{
		if(this->val[i]>target.val[i])
		{
			return true;
		}
		if(this->val[i]<target.val[i])
		{
			return false;
		}
	}

	return false; //< or ==
}
bool bignum::operator==(const bignum& target) const
{
	if(this->val.size()!=target.val.size())
	{
		return false;
	}
	for(int i=0;i<this->val.size();i++)
	{
		if(this->val[i]!=target.val[i])
		{
			return false;
		}
	}
	return true;
}

class cell
{
public:
	int row;
	int col;
	signedbignum finalrst;
	bool hasrst;
	string expr;
	void setdata(int r,int c,string e)
	{
		row=r;
		col=c;
		expr=e;
	}
	cell()
	{
		hasrst=false;
	}
};
class excel
{
private:
	int ncol;
	int nrow;
	
public:
	cell* aray[MAXROW][MAXCOL];

	//Create a new Excel spredsheet widh r * c cells
	excel(int r,int c):nrow(r),ncol(c)
	{
		int i,j;
		for(i=0;i<nrow;i++)
		{
			for(j=0;j<ncol;j++)
			{
				aray[i][j]=new cell;
			}
		}
	}
	~excel()
	{
		int i,j;
		for(i=0;i<nrow;i++)
		{
			for(j=0;j<ncol;j++)
			{
				delete aray[i][j];
			}
		}
	}
	signedbignum eval(int r,int c);
};
excel* sheet;


class symbol
{
public:
	virtual signedbignum eval()=0;
	symbol* left;
	symbol* right;
};

class oter:public symbol
{
public:
	otype type;
	signedbignum eval()
	{
		signedbignum l,r;
		if(left!=NULL)
		{
			l=left->eval();
		}else
		{
			if(type==oadd || type==ominus || type==lpar)
			{
				l=signedbignum((int)0);
			}else
			{
				l=signedbignum((int)1);
			}
		}
		if(right!=NULL)
		{
			r=right->eval();
		}else
		{
			if(type==oadd || type==ominus || type==lpar)
			{
				r=signedbignum((int)0);
			}else
			{
				r=signedbignum((int)1);
			}
		}
		signedbignum rst;
		switch(type)
		{
		case oadd:
			rst=l+r;
			break;
		case ominus:
			rst=l-r;
			break;
		case otime:
			rst=l*r;
			break;
		case odivide:
			rst=l/r;
			break;
		case lpar:
			rst=l;
			break;
		}
		return rst;
	}
};

class oand:public symbol
{
public:
	int row;
	int col;
	signedbignum eval();
};
class oconst:public oand
{
public:
	signedbignum value;
	signedbignum eval()
	{
		return value;
	}
};




class cellparser
{
private:
	list<symbol*> symlink;
	string expr;
	int cursor;
	oand* getoand()
	{
		int nrow=0;
		int ncol=0;
		bool hasalpha=false;
		while(isalpha(expr[cursor]))
		{
			hasalpha=true;
			ncol*=26;
			ncol+=(int)(expr[cursor]-'A');
			cursor++;
		}
		while(expr[cursor]>='0' && expr[cursor]<='9')
		{
			nrow*=10;
			nrow+=(int)(expr[cursor]-'0');
			cursor++;
		}
		nrow-=1;
		if(hasalpha)
		{
			oand* rst= new oand;
			rst->row=nrow;
			rst->col=ncol;
			return rst;
		}else
		{
			oconst* rst= new oconst;
			rst->value=signedbignum(nrow+1);
			return rst;
		}
	}
	oter* getoter()
	{
		oter* rst=new oter;
		switch(expr[cursor])
		{
		case '+':
			rst->type=oadd;
			break;
		case '-':
			rst->type=ominus;
			break;
		case '*':
			rst->type=otime;
			break;
		case '/':
			rst->type=odivide;
			break;
		case '(':
			rst->type=lpar;
			break;
		case ')':
			rst->type=rpar;
			break;
		}
		cursor++;
		return rst;
	}
	symbol* buildtree3()
	{
		symbol* root=NULL;
		symbol* stemp=NULL;
		

		stemp=symlink.front();
		oter* o=dynamic_cast<oter*>(stemp);
		if(o==NULL)
		{
			symlink.pop_front();
			root=stemp;
		}else if(o->type==lpar)
		{
			symlink.pop_front();
			o->left=buildtree();
			o->right=NULL;
			root=o;
			stemp=symlink.front();
			oter* o=dynamic_cast<oter*>(stemp);
			if(o!=NULL&&o->type==rpar)
			{
				symlink.pop_front();
			}
		}
		return root;
	}
	symbol* buildtree2()
	{
		symbol* root=NULL;
		symbol* stemp=NULL;
		
		root=buildtree3();
		while(!symlink.empty())
		{
			stemp=symlink.front();
			oter* o=dynamic_cast<oter*>(stemp);
			if(o->type==otime || o->type==odivide)
			{
				symlink.pop_front();
				o->left=root;
				o->right=buildtree3();
				root=o;
			}else
			{
				break;
			}
		}
		return root;
	}
	symbol* buildtree()
	{
		symbol* root=NULL;
		symbol* stemp=NULL;
		
		root=buildtree2();
		while(!symlink.empty())
		{
			symbol* stemp=symlink.front();
			oter* o=dynamic_cast<oter*>(stemp);
			if(o->type==oadd || o->type==ominus)
			{
				symlink.pop_front();
				o->left=root;
				o->right=buildtree2();
				root=o;
			}else
			{
				break;
			}
		}
		return root;
	}
public:
	cellparser(string expression):expr(expression)
	{
		cursor=0;
	}
	signedbignum getresult()
	{
		//Parse stage
		if(expr[cursor]=='e')
		{
			cursor=1;
		}else
		{
			//pure number
			return signedbignum(expr);
		}
		
		while(1)
		{
			if(isalpha(expr[cursor]) || (expr[cursor]>='0' && expr[cursor]<='9'))
			{
				symlink.push_back(getoand());
			}else if(expr[cursor]=='+' || expr[cursor]=='-' || expr[cursor]=='*' || expr[cursor]=='/' || expr[cursor]=='(' || expr[cursor]==')')
			{
				symlink.push_back(getoter());
			}
			//next symbol
			if(cursor==expr.length())  //end?
			{
				break;
			}
		}
		//build tree
		symbol* root=NULL;

		root=buildtree();

		//now eval
		return root->eval();
	}
};
signedbignum oand::eval()
{
	//return atoi(sheet->aray[row][col]->expr.c_str());
	if(sheet->aray[row][col]->hasrst==false)
	{
		sheet->aray[row][col]->hasrst=true;
		cellparser a(sheet->aray[row][col]->expr);
		sheet->aray[row][col]->finalrst=a.getresult();
		
	}
	return sheet->aray[row][col]->finalrst;
}
signedbignum excel::eval(int r,int c)
{
	cell* now=aray[r][c];
	cellparser a(now->expr);
	return a.getresult();
}


int main(void)
{
	int ncase;
	scanf("%d",&ncase);
	

	for(int i=0;i<ncase;i++)
	{
		int nrow,ncol;
		scanf("%d",&nrow);
		scanf("%d",&ncol);


		sheet=new excel(nrow,ncol);

		//Read
		for(int j=0;j<nrow;j++)
		{
			for(int k=0;k<ncol;k++)
			{
				char buffer[1000];
				scanf("%s",buffer);
				
				sheet->aray[j][k]->setdata(j,k,buffer);
			}
		}
		//Parse

		for(int j=0;j<nrow;j++)
		{
			for(int k=0;k<ncol;k++)
			{
				printf("%s",sheet->eval(j,k).output().c_str());
				if(k!=ncol-1)
				{
					printf(" ");
				}
			}
			printf("\n");
		}
		delete sheet;
		if(i!=ncase-1)
		{
			printf("\n");
		}
	}
	return 0;
}

I can pass sample input, and after testing my own input for weeks, I still can not understand where I did it wrong.
I even tried large number manipulation, but still in vain.
Can anyone tell me where I get wrong or tell me a input that fails my program?
The judge is screwing me up
Thanks!