当前位置:网站首页>BUAA计算器(表达式计算-表达式树实现)
BUAA计算器(表达式计算-表达式树实现)
2022-07-06 03:23:00 【star-399】
【问题描述】
从标准输入中读入一个整数算术运算表达式,如24 / ( 1 + 2 + 36 / 6 / 2 - 2) * ( 12 / 2 / 2 )= ,计算表达式结果,并输出。
要求:
1、表达式运算符只有+、-、*、/,表达式末尾的=字符表示表达式输入结束,表达式中可能会出现空格;
2、表达式中会出现圆括号,括号可能嵌套,不会出现错误的表达式;
3、出现除号/时,以整数相除进行运算,结果仍为整数,例如:5/3结果应为1。
4、要求采用表达式树来实现表达式计算。
表达式树(expression tree):
我们已经知道了在计算机中用后缀表达式和栈来计算中缀表达式的值。在计算机中还有一种方式是利用表达式树来计算表达式的值。表达式树是这样一种树,其根节点为操作符,非根节点为操作数,对其进行后序遍历将计算表达式的值。由后缀表达式生成表达式树的方法如下:
l 读入一个符号:
l 如果是操作数,则建立一个单节点树并将指向他的指针推入栈中;
l 如果是运算符,就从栈中弹出指向两棵树T1和T2的指针(T1先弹出)并形成一棵新树,树根为该运算符,它的左、右子树分别指向T2和T1,然后将新树的指针压入栈中。
例如输入的后缀表达为:
ab+cde+**
则生成的表达式树为:
【输入形式】
从键盘输入一个以=结尾的整数算术运算表达式。操作符和操作数之间可以有空格分隔。
【输出形式】
首先在屏幕上输出表达式树根、左子节点及右子节点上的运算符或操作数,中间由一个空格分隔,最后有一个回车(如果无某节点,则该项不输出)。然后输出表达式计算结果。
【样例输入】
24 / ( 1 + 2 + 36 / 6 / 2 - 2) * ( 12 / 2 / 2 ) =
【样例输出】
*/ /
18
【样例说明】
按照运算符及括号优先级依次计算表达式的值。在生成的表达树中,*是根节点的运算符,/ 是根节点的左子节点上运算符,/是根节点的右子节点上运算符,按题目要求要输出。
#include <ctype.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct numop
{
// define elemnet
int num;
char op;
} sto[501];
struct opstack
{
// define stack
int top;
struct numop sto[500];
};
struct Tree
{
// define Tree
int n;
char o;
struct Tree *l;
struct Tree *r;
};
struct tree_pro
{
// tree stack
struct Tree tree[502];
int top;
} t;
typedef struct opstack stack;
stack o; // operation
struct Tree *u, *v, *w; // temporary struct
char c;
int i, j, k, n;
void initstack(stack *s)
{
// init stack
s->top = -1;
}
void push_tree(struct tree_pro *t, int m,
char c)
{
// stack in member and operation
if (m != -1)
{
t->tree[++t->top].l = NULL;
t->tree[t->top].r = NULL;
t->tree[t->top].n = m;
t->tree[t->top].o = 0;
}
else
{
u = (struct Tree *)malloc(sizeof(struct Tree));
v = (struct Tree *)malloc(sizeof(struct Tree));
w = (struct Tree *)malloc(sizeof(struct Tree));
memcpy(v, &t->tree[t->top--], sizeof(struct Tree));
memcpy(u, &t->tree[t->top], sizeof(struct Tree));
w->o = c;
switch (c)
{
case '+':
w->n = u->n + v->n;
break;
case '-':
w->n = u->n - v->n;
break;
case '*':
w->n = u->n * v->n;
break;
case '/':
w->n = u->n / v->n;
break;
}
w->l = (struct Tree *)&u;
w->r = (struct Tree *)&v;
memcpy(&t->tree[t->top], w, sizeof(struct Tree));
}
}
void pushstack_o(stack *o, struct tree_pro *t, int m,
char c)
{
// stack in member and operation
if (m <= o->sto[o->top].num && o->sto[o->top].num != 3)
{
for (; o->sto[o->top].num != 3;)
{
if (m > o->sto[o->top].num)
break;
push_tree(t, -1, o->sto[o->top].op);
o->top--;
if (o->top == -1)
break;
}
}
if (m == 4)
{
// right round
for (; o->sto[o->top].num != 3; o->top--)
{
push_tree(t, -1, o->sto[o->top].op);
}
o->top--;
}
else
{
o->sto[++o->top].num = m; // save number and operation
o->sto[o->top].op = c;
}
}
void print_tree(struct tree_pro *t)
{
if (t->tree[t->top].o != 0)
printf("%c ", t->tree[t->top].o);
else
printf("%d ", t->tree[t->top].n);
if (u->o != 0)
printf("%c ", u->o);
else
printf("%d ", u->n);
if (v->o != 0)
printf("%c \n", v->o);
else
printf("%d \n", v->n);
printf("%d", t->tree[t->top].n);
}
int main()
{
initstack(&o); // init all, num, operation
t.top = -1;
while ((c = getchar()) != '=')
{
if (c >= '0' && c <= '9')
{
for (i = 0; c >= '0' && c <= '9'; c = getchar()) // number produce
n = c - '0' + n * 10;
ungetc(c, stdin);
push_tree(&t, n, 0); // stack in
n = 0;
}
else if (c != ' ')
{
switch (c)
{
// distribute number
case '+':
pushstack_o(&o, &t, 1, c);
break;
case '-':
pushstack_o(&o, &t, 1, c);
break;
case '*':
pushstack_o(&o, &t, 2, c);
break;
case '/':
pushstack_o(&o, &t, 2, c);
break;
case '(':
pushstack_o(&o, &t, 3, c);
break;
case ')':
pushstack_o(&o, &t, 4, c);
break;
}
}
}
for (; o.top != -1; o.top--)
{
push_tree(&t, -1, o.sto[o.top].op);
}
print_tree(&t);
return 0;
}
BUAAer?
边栏推荐
- Problems encountered in 2022 work IV
- 多态day02
- Redis cache breakdown, cache penetration, cache avalanche
- 3857墨卡托坐标系转换为4326 (WGS84)经纬度坐标
- 【SLAM】ORB-SLAM3解析——跟踪Track()(3)
- Brush questions in summer -day3
- 电机控制反Park变换和反Clarke变换公式推导
- Analyze 菜单分析
- three. JS page background animation liquid JS special effect
- Leetcode problem solving -- 98 Validate binary search tree
猜你喜欢
随机推荐
XSS challenges bypass the protection strategy for XSS injection
3.1 rtthread 串口设备(V1)详解
Performance test method of bank core business system
Exness foreign exchange: the governor of the Bank of Canada said that the interest rate hike would be more moderate, and the United States and Canada fell slightly to maintain range volatility
Eight super classic pointer interview questions (3000 words in detail)
Audio audiorecord binder communication mechanism
js凡客banner轮播图js特效
SD卡报错“error -110 whilst initialising SD card
【Rust 笔记】18-宏
Pytorch基础——(2)张量(tensor)的数学运算
Descriptor implements ORM model
An article about liquid template engine
February 14, 2022 Daily: Google long article summarizes the experience of building four generations of TPU
BUUCTF刷题笔记——[极客大挑战 2019]EasySQL 1
Brush questions in summer -day3
数据分析——seaborn可视化(笔记自用)
OCR文字識別方法綜述
Lua uses require to load the shared library successfully, but the return is Boolean (always true)
MPLS experiment
Mysql database operation