表达式转二叉树并三种模式输出

www.MyException.Cn  网友分享于：2013-02-20  浏览：3次

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define N 100
//将中缀表达式转换为前缀表达式。
typedef struct Node
{
char key;
struct Node * left;
struct Node * right;
}Node;
//search for the operator with the highest grade in a
int search(char a[], int begin, int end)
{
int tag = -1;
int isInBrackets = 0;//是否在括号里面
if(a[begin] == '(' && a[end] == ')')
{
begin += 1;
end -= 1;
}
int amExist = 0;//是否存在。
for(int i = begin; i < end; i++)
{
if(a[i] == '(')
isInBrackets++;
if(a[i] == ')')
isInBrackets--;
if((a[i] == '+' || a[i] == '-') && isInBrackets == 0)
{
tag = i;
amExist = 1;
}
if((a[i] == '*' || a[i] == '/') && isInBrackets == 0 && amExist == 0)
{
tag = i;
}
}
return tag;
}
//build the binary tree
Node * buildBinaryTree(char a[], int begin, int end)
{
Node * p = NULL;
if(begin == end)
{
p = (Node *)malloc(sizeof(Node));
p->key = a[begin];
p->left = NULL;
p->right = NULL;
}
else
{
int tag;
tag = search(a,begin,end);
if (tag<0) {
printf("对不起，请输入正确的表达式。");
return NULL;//tag小于0的时候不是表达式。
}
p = (Node *)malloc(sizeof(Node));
p->key = a[tag];
if(a[begin] == '(' && a[end] == ')')
{
begin += 1;
end -= 1;
}
p->left = buildBinaryTree(a, begin, tag - 1);
p->right = buildBinaryTree(a, tag + 1, end);
}
return p;
}
{
{
}
}
{
{

}
}
{
{

}
}

int main()
{
char input[N];
while(scanf("%s", input))
{
if(strcmp(input, "exit") == 0)
{
break;
}
int length = (int)strlen(input);
head = buildBinaryTree(input, 0, length - 1);
printf("前缀输出为：\n");
printf("\n中缀输出为：\n");
printf("\n后缀输出为：\n");
printf("\n");
}

return 0;
}