5.3 计算器（表达式计算-表达式树实现）
【问题描述】
从标准输入中读入一个整数算术运算表达式，如24 / ( 1 + 2 + 36 / 6 / 2 – 2) * ( 12 / 2 / 2 )= ，计算表达式结果，并输出。
要求：
表达式运算符只有+、-、*、/，表达式末尾的=字符表示表达式输入结束，表达式中可能会出现空格；
表达式中会出现圆括号，括号可能嵌套，不会出现错误的表达式；
出现除号/时，以整数相除进行运算，结果仍为整数，例如：5/3结果应为1。
要求采用表达式树来实现表达式计算。
表达式树（expression tree）：
我们已经知道了在计算机中用后缀表达式和栈来计算中缀表达式的值。在计算机中还有一种方式是利用表达式树来计算表达式的值。表达式树是这样一种树，其根节点为操作符，非根节点为操作数，对其进行后序遍历将计算表达式的值。由后缀表达式生成表达式树的方法如下：
读入一个符号：
如果是操作数，则建立一个单节点树并将指向他的指针推入栈中；
如果是运算符，就从栈中弹出指向两棵树T1和T2的指针（T1先弹出）并形成一棵新树，树根为该运算符，它的左、右子树分别指向T2和T1，然后将新树的指针压入栈中。
例如输入的后缀表达为：
ab+cde+**
则生成的表达式树为：
【输入形式】
从键盘输入一个以=结尾的整数算术运算表达式。操作符和操作数之间可以有空格分隔。
【输出形式】
首先在屏幕上输出表达式树根、左子节点及右子节点上的运算符或操作数，中间由一个空格分隔，最后有一个回车（如果无某节点，则该项不输出）。然后输出表达式计算结果。
【样例输入】
24 / ( 1 + 2 + 36 / 6 / 2 – 2) * ( 12 / 2 / 2 ) =
【样例输出】
-
/ /
18
【样例说明】
按照运算符及括号优先级依次计算表达式的值。在生成的表达树中，*是根节点的运算符，/ 是根节点的左子节点上运算符，/是根节点的右子节点上运算符，按题目要求要输出。
思路
代码
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX 300 //my chinese input method is broken at halfway so I use EN note.
enum type // enum is very NB.so I want to use it. and this is a sign
{
number,
operator, };
union element //union is so SB so I use enum to help it.
{
int a;
char b;
};
typedef struct elem
{
union element a;
enum type b;
} NBelem; //this is the expression element by element
struct tree
{
NBelem a; //I finally use typedef
struct tree *lchild, *rchild;
};
//this is finally the tree of expression element by element
char op[MAX], data[MAX]; //op,opfg栈用于中缀转后缀 数据ndata符号data 为4.3成果
short opfg[MAX]; //(((((((((((((((((((((((((((((just like the enum sign
int top = -1;
int ndata[MAX];
struct tree root;
struct tree *trees[MAX]; //this time we should create a pointer stack!!!!!!!
||||||||||||The above is indeed data structure||||||||||
//next is programming:::::///
4.3
void push(char c, char fg)
{
top++;
op[top] = c;
opfg[top] = fg;
}
char pop(void)
{
char c = op[top];
top--;
return c;
}
/this time we should create function for a pointer stack!!!!!!!
void nbpush(struct tree *tmp)
{
top++;
trees[top] = tmp;
}
struct tree *nbpop(void)
{
struct tree *tmp = trees[top];
top--;
return tmp;
}
int T3ofassignment4(void); //4.3 ndata存数只是个字典 data存字符哦 俩数组加起来才是表达式
int calculate(struct tree *t);
int main()
{
int N = (T3ofassignment4());
/*************************************************
At this time !data! and !ndata! forms the expression
!data! 's order is right(same as expression)
!ndata!'s order is wrong(elements one next to one) it seems like a dictionary
!top! =-1 and stack!trees[]!will be used
************************************************/
int i, j = 0;
//开始建树
top = -1;
for (i = 0; i < N; i++)
{
if (data[i] == 1) //expression element is number
{
struct tree *tmpp; //this tmp just use to push it into the trees
tmpp = (struct tree *)malloc(sizeof(struct tree));
tmpp->lchild = NULL;
tmpp->rchild = NULL;
tmpp->a.a.a = ndata[j++]; //don't be scared by .a.a.a
tmpp->a.b = number; ///HAHAHA this is a number
nbpush(tmpp); //GET IN!!! GET IN!!!
}
else
{
struct tree *tmpp; //this tmp just use to push it into the trees
tmpp = (struct tree *)malloc(sizeof(struct tree));
tmpp->rchild = nbpop(); //don't be scared by .a.a.a
tmpp->lchild = nbpop();
tmpp->a.a.b = data[i]; //don't be scared by .a.a.b
tmpp->a.b = operator; ///HAHAHA this is a operator
nbpush(tmpp); //GET IN!!! GET IN!!!
}
}
root = *trees[0];
The expression tree has been generated
printf("%c ", root.a.a); //this is not safe (SB union
if (root.lchild->a.b == operator)
printf("%c ", root.lchild->a.a.b);
else
printf("%d ", root.lchild->a.a.a);
if (root.rchild->a.b == operator)
printf("%c", root.rchild->a.a.b);
else
printf("%d", root.rchild->a.a.a);
printf("\n");
//start the calculation
//((((((((((((((((((((((((()))))))))))))))))))))))))
printf("%d", calculate(&root));
system("pause");
return 0;
}
int calculate(struct tree *t)
{
//recursion is NBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB
/** N N BB B
* N N N B B
* N N N BBB
* N N N B B
* N N BB B */
if (t->a.b == number)
return t->a.a.a;
else if (t->a.a.b == '+')
return calculate(t->lchild) + calculate(t->rchild);
else if (t->a.a.b == '-')
return calculate(t->lchild) - calculate(t->rchild);
else if (t->a.a.b == '*')
return calculate(t->lchild) * calculate(t->rchild);
else if (t->a.a.b == '/')
return calculate(t->lchild) / calculate(t->rchild);
else if (t->a.a.b == '%')
return calculate(t->lchild) % calculate(t->rchild);
}
int T3ofassignment4()
{
int i = 0, j = 0, opfg1 = 0, num = 0, N = 0; //data存表达式负号的是符号 i控制data
char c = 0;
while (1) 转化开始 存到data[i]中
{
c = getchar();
if (c == '=')
break;
if (c >= '0' && c <= '9')
{
num = 0;
while (c >= '0' && c <= '9')
{
num = 10 * num + c - '0';
c = getchar();
}
data[i++] = 1;
ndata[j++] = num;
if (c == '=')
break;
}
if (c != ' ')
{
if (c == '+' || c == '-')
opfg1 = 1;
else if (c == '*' || c == '/' || c == '%')
opfg1 = 2;
else if (c == '(')
opfg1 = 3;
if (c == ')') //开始操作c
{
while (opfg[top] != 3)
{
data[i++] = pop(); //()内出栈
}
pop();
opfg1 = 0; //初始化一下因为不用他了
}
else if (opfg[top] == 3) //栈顶是（
{
push(c, opfg1); //直接入栈
}
else if (opfg1 <= opfg[top]) //栈顶优先级更高的情况
{
while (opfg1 <= opfg[top] && opfg[top] != 3)
data[i++] = pop();
push(c, opfg1);
}
else if (opfg1 > opfg[top]) //栈顶优先级低的情况
{
push(c, opfg1); //直接入栈
}
}
}
while (top != -1)
{
data[i++] = pop();
}
N = i;
return N;
}