1259.cpp

这是哈尔滨工业大学acmOJ的源代码

/*  This Code is Submitted by wywcgs for Problem 1259 on 2005-10-19 at 08:59:30 */ 
#include <cstdio>
#include <cstring>
#define  MAX  256
#define  LIMIT  64

class BSTreeNode {
public:
	char operate;
	bool isOperator;
	int value;
	BSTreeNode *left;
	BSTreeNode *right;
	void init(int v, bool iso, char o) {
		value = v;
		isOperator = iso;
		operate = o;
		left = right = NULL;
	}
	void visit() {
		if(left != NULL) {
			left->visit();
		}
		if(isOperator) {
			printf("%c ", operate);
		} else {
			printf("%d ", value);
		}
		if(right != NULL) {
			right->visit();
		}
	}
	void compute() {
		int lv = left->value;
		int rv = right->value;
		left = right = NULL;
		isOperator = false;
		switch(operate) {
		case '+':
			value = lv + rv;
			break;
		case '-':
			value = lv - rv;
			break;
		case '*':
			value = lv * rv;
			break;
		default:
			value = lv / rv;
			break;
		}
	}
};

int prior(char);

int main()
{
	BSTreeNode *Node[LIMIT], *root, *t, *p;
	int lowQueue[LIMIT], lb, lt;
	int highQueue[LIMIT], hb, ht;
	int i, v, N, k, x = 0;
	bool op;
	char o, varName[LIMIT];
	
	for(i = 0; i < LIMIT; i++) {
		Node[i] = new BSTreeNode;
	}
	while(true) {
		lb = lt = hb = ht = 0;
		root = NULL;
		for(N = 0, op = false; ; op = !op, N++) {
			if(op) {
				scanf("%c", &o);
				if(o == '=') {
					scanf("%s", varName);
					break;
				} else {
					Node[N]->init(-1, true, o);
					if(prior(o) == 1) {
						lowQueue[lb++] = N;
					} else {
						highQueue[hb++] = N;
					}
					if(root == NULL) {
						root = Node[N];
						root->left = t;
					} else {
						if(prior(root->operate) < prior(o)) {
							Node[N]->left = root->right;
							root->right = Node[N];
						} else {
							Node[N]->left = root;
							root = Node[N];
						}
					}
				}
			} else {
				if(scanf("%d\n", &v) != 1) {
					return 0;
				}
				Node[N]->init(v, false, '\0');
				if(root == NULL) {
					t = Node[N];
				} else {
					for(p = root; ; p = p->right) {
						if(p->right == NULL) {
							p->right = Node[N];
							break;
						}
					}
				}
			}
		}
		if(x != 0) {
			putchar('\n');
		}
		x++;
		root->visit();
		printf("= %s\n", varName);
		while(true) {
			if(hb != ht) {
				k = highQueue[ht++];
			} else if(lb != lt) {
				k = lowQueue[lt++];
			} else {
				break;
			}
			Node[k]->compute();
			root->visit();
			printf("= %s\n", varName);
		}
	}
	
	return 0;
}

int prior(char op)
{
	switch(op) {
	case '*': case '/':
		return 2;
	case '+': case '-':
		return 1;
	default:
		return 0;
	}
}