1038.cpp

哈尔滨工业大学ACM 竞赛网上在线试题集锦的源代码

/*  This Code is Submitted by wywcgs for Problem 1038 on 2006-01-18 at 03:22:41 */ 
#include <cstdio>
#include <cstring>
#include <cctype>
#include <algorithm>
using namespace std;

char nextChar();
int pri(const char);

class SignTree {
private:
	bool needPare(const SignTree*, bool) const;
public:
	SignTree *left, *right;
	SignTree();
	SignTree(const char);
	bool isOperator;
	char op, var;
	void print();
};
SignTree::SignTree() {
	char ch = nextChar();
	left = right = NULL;
	isOperator = false;
	if(ch == '(') left = new SignTree();
	else left = new SignTree(ch);
	SignTree *p = this, *t;
	while((ch = nextChar()) != ')' && ch != '\n') {
		if(right == NULL) op = ch, isOperator = true;
		else {
			int pc = pri(ch), pp = pri(p->op);
			if(pc > pp) {
				t = p->right; p->right = new SignTree(ch);
				p->right->left = t; p = p->right;
			} else {
				if(pc < pp) p = this;
				t = new SignTree(ch); swap(*p, *t); p->left = t;
			}
		}
		if((ch = nextChar()) == '(') p->right = new SignTree();
		else p->right = new SignTree(ch);
	}
	if(right == NULL) { p = left; *this = *p; delete p; }
}
SignTree::SignTree(const char ch) {
	if(isalpha(ch)) isOperator = false, var = ch;
	else isOperator = true, op = ch;
	left = right = NULL;
}
void SignTree::print() {
	if(!isOperator) putchar(var);
	else {
		bool lnp = needPare(left, false), rnp = needPare(right, true);
		if(lnp) putchar('('); left->print(); if(lnp) putchar(')');
		putchar(op);
		if(rnp) putchar('('); right->print(); if(rnp) putchar(')');
		delete left; delete right;
	}
}
bool SignTree::needPare(const SignTree* node, bool equ) const {
	if(op == '+' || op == '*') equ = false;
	if(node->isOperator && 
		(pri(node->op) < pri(op) || (equ && pri(node->op) == pri(op)))) return true;
	else return false;
}

int main()
{
	int t, T;
	SignTree *root;

	scanf("%d", &T);
	for(t = 0; t < T; t++) {
		scanf("\n");
		root = new SignTree();
		root->print();
		putchar('\n');
		delete root;
	}
	
	return 0;
}
char nextChar()
{
	char ch = ' ';
	while(ch == ' ' || ch == '\t') ch = getchar();
	return ch;
}
int pri(const char op)
{
	switch(op) {
	case '+': case '-': return 0;
	default: return 1;
	}
}