求C++ 表达式求值得程序，最好简单说明数据结构和大致方法

Question

如题所述

Answer 1

将操作数作为二叉树的叶子结点，操作符作为二叉树的非叶子结点
先序遍历则得到前缀式
中序遍历则得到中缀式
后序遍历则得到后缀式
//以(a+b)/c-d+e*f进行演示
+
(-
*)
(/
d)
(e
f)
(+
c)
(a
b)
#include
<stdio.h>
#include
<stdlib.h>
typedef
char
Elem;
typedef
struct
Node
{
Elem
data;
struct
Node
*pLchild;
struct
Node
*pRchild;
}BTreeNode,
*BTree;
BTree
CreateBTree(BTree
T,
Elem
*str)//创建二叉树
{
static
int
i
=
0;
if
('0'
==
str[i])
{
T
=
NULL;
}
else
{
T
=
(BTree)
malloc
(sizeof(BTreeNode));
T->data
=
str[i++];
T->pLchild
=
CreateBTree(T->pLchild,
str);
i++;
T->pRchild
=
CreateBTree(T->pRchild,
str);
}
return
T;
}
void
PostTraverseBTree(BTree
T)//后序
{
if
(NULL
!=
T)
{
PostTraverseBTree(T->pLchild);
PostTraverseBTree(T->pRchild);
printf("%c
",
T->data);
}
}
void
InTraverseBTree(BTree
T)//中序
{
if
(NULL
!=
T)
{
InTraverseBTree(T->pLchild);
printf("%c
",
T->data);
InTraverseBTree(T->pRchild);
}
}
void
PreTraverseBTree(BTree
T)//前序
{
if
(NULL
!=
T)
{
printf("%c
",
T->data);
PreTraverseBTree(T->pLchild);
PreTraverseBTree(T->pRchild);
}
}
int
main(void)
{
BTree
T
=
NULL;
Elem
str[]
=
"+-/+a00b00c00d00*e00f00";
T
=
CreateBTree(T,
str);
printf("\n\n");
printf("先序遍历(前缀式):\n");
PreTraverseBTree(T);
printf("\n\n");
printf("中序遍历(中缀式):\n");
InTraverseBTree(T);
printf("\n\n");
printf("后序遍历(后缀式):\n");
PostTraverseBTree(T);
printf("\n\n");
}