做一编译原理题。

#include
#include

int num = 1;
typedef struct treeRep *Tree;
typedef struct treeRep Node;

struct treeRep {
char value;
Node *left;
Node *right;
};

Node *newNode(char v)
{
Node *n;
n = malloc(sizeof(struct treeRep));
assert(n != NULL);
n->value = v;
n->left = NULL;
n->right = NULL;

return n;
}

Tree parse(char* input,int index,Tree t)
{
assert(t != NULL);
if(input[index] == '\0') return t;

char currentOp = input[index++];

Node *currentVal = newNode(input[index++]);
Tree top = newNode(currentOp);

if(currentOp == '+' || currentOp == '-' || t->right == NULL){
top->left = t;
top->right = currentVal;

}else{

top->left = t->right;
top->right = currentVal;
t->right = top;
return parse(input, index, t);
}

return parse(input, index,top);
}

void addT(Tree t){
t->left = NULL;
t->right = NULL;
if(t->value >= '1' && t->value <= '9' ) printf("t");
printf("%c,",t->value);
}

void traverse(Tree t){

assert(t!=NULL);
if(t->left != NULL){

traverse(t->left);
traverse(t->right);

//assert(t->left->left == NULL);
// && t->left->right == NULL);
assert(t->value=='+' || t->value=='-' || t->value=='*' || t->value=='/');

printf("%d.(%c,",num,t->value);
addT(t->left);
addT(t->right);
printf("t%d)\n",num);

t->value = (char)(num+'0');
num++;

}else{
assert(t->right == NULL);
}
}

int main(void){
char input[20];
scanf("%s",input);
Tree t = newNode(input[0]);

traverse(parse(input,1,t));
system("pause");
return 0;
}

表达式求值问题，用栈来做。根据运算符的优先级来判断每次操作。
可以用两个栈，一个放运算符，一个放操作数。