#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;
}
void outputBinaryTree_pre(Node * head)
{
if(head)
{
printf("%c", head->key);
outputBinaryTree_pre(head->left);
outputBinaryTree_pre(head->right);
}
}
void outputBinaryTree_in(Node * head)
{
if(head)
{
outputBinaryTree_in(head->left);
printf("%c", head->key);
outputBinaryTree_in(head->right);
}
}
void outputBinaryTree_post(Node * head)
{
if(head)
{
outputBinaryTree_post(head->left);
outputBinaryTree_post(head->right);
printf("%c", head->key);
}
}
int main()
{
printf("please input a expression:");
char input[N];
while(scanf("%s", input))
{
if(strcmp(input, "exit") == 0)
{
break;
}
Node * head = NULL;
int length = (int)strlen(input);
head = buildBinaryTree(input, 0, length - 1);
printf("前缀输出为:\n");
outputBinaryTree_pre(head);//这个必须放在在里面,因为他是一个个输出的。
printf("\n中缀输出为:\n");
outputBinaryTree_in(head);//这个必须放在在里面,因为他是一个个输出的。
printf("\n后缀输出为:\n");
outputBinaryTree_post(head);//这个必须放在在里面,因为他是一个个输出的。
printf("\n");
}
return 0;
}
- 浏览: 1350359 次
- 性别:
- 来自: 开封
最新评论
-
用户6006038975:
macd2666 写道录制出来的语音声音好轻啊。你好,这个编译 ...
ios音频录制和播放,文件很小。压缩效果不错 -
用户6006038975:
macd2666 写道录制出来的语音声音好轻啊。
ios音频录制和播放,文件很小。压缩效果不错 -
用户6006038975:
linker command failed with exit ...
ios音频录制和播放,文件很小。压缩效果不错 -
mapboo:
http://www.codertopic.com/?page ...
史上最全的iOS面试题及答案 -
macd2666:
录制出来的语音声音好轻啊。
ios音频录制和播放,文件很小。压缩效果不错
相关推荐
输入一个前缀或后缀表达式 输出一个相应二叉树
选择输入前中后缀表达式,建立表达式二叉树,再前序中序后序遍历二叉树,输出三种形式的表达式
一个 表达式和一棵二叉树之间,存在着自然的对应关系。我需要写一个程序,实现基于二叉树表示的算术表达式的操作。 1.2这个算法的要求 假设算术表达式Expression内可以含有变量(a~z)、常量(0~9)和二元运算符(+,,*...
根据逆波兰表达式将各序表达式显示出来,并且将二叉树输出
给定一个表达式,输出其中缀表达式,利用了栈和二叉树,是理解数据结构很好的资料
程序根据后缀表达式建立二叉树,建立过程中用到了栈,并分别采取递归和非递归的方法,对二叉树进行了先序、中序、后续遍历。
输入一表达式,将其用表达式树表示,并用表达式数计算表达式的值。
(1) ReadExpre(E)- _以字符序列的形式输入语法正确的前缀表达式并构 造表达式 E。(2) WriteExpre(E)- 用带括弧的中缀表达式输出表达式 E。 (3) Assign(V,c)-实现对变量 V 的赋值(V=c), 变量的初值为 0。 (4) Value...
数据结构的课程设计,输入字符串的算术表达式,以二叉树的形式存储算术表达式,计算表达式结果并输出
根据括号表达式构造二叉树,对二叉树进行前序,中序,后序,层序遍历,并用树形方式打印输出,有详细注释,供C++数据结构课程学习与交流使用。
将给定的表达式树(二叉树)转换为等价的中缀表达式(通过括号反映操作符的计算次序)并输出
输入中缀表达式 输出后缀表达式树 VC6.0
1. ReadExpr(E)——以字符序列的形式输入语法正确的前缀表示式并构造表达式E。 2. WriteExpr(E)——用带括号的中缀表示式输出表达式E。 3. Assign(V,c)——实现对变量V的赋值(V=c),变量的初值为0。 4. Value...
1.输入一个中缀表达式,构造表达式树,以文本方式输出树结构。 输入:例如,输入a+b+c*(d+e) 输出:以缩进表示二叉树的层次,左(根),右(叶),上(右子树),下(左子树) 2.编写二叉树类的成员函数,分别实现...
一个表达式和一棵二叉树之间,存在着自然的对应关系。写一个程序,实现 基于二叉树表示的算术表达式Expression的操作。 假设算术表达式Expression内可以含有变量(a-z),常量(0-9)和二元运算符(+,-,*,/,^...
将中序表达式转化为二叉树的形式,并用前序表达式,后序表达式,逐层遍历输出这个树,并将结果计算出来。 如2*3/(2-1)+5*(4-1) ===> +/* 2 3 - 2 1 * 5 - 4 1 == 21
问题描述(功能要求): 功能: 编写完整程序,将中缀表达式翻译成后缀表达式。表达式由操作数 ( 变量 ) 、操作 ( 运算符 ) 以及小括弧 “ ( ” 和 “ ) ” 组成,其中...2)利用二叉树把中缀表达式转化为前缀表达式
1. ReadExpr(E)——以字符序列的形式输入语法正确的前缀表示式并构造表达式E。 2. WriteExpr(E)——用带括号的中缀表示式输出表达式E。 3. Assign(V,c)——实现对变量V的赋值(V=c),变量的初值为0。 4. Value...
建立一棵二叉树,试编程实现...2. 对这棵二叉树进行遍历:先序、中序、后序以及层次遍历,分别输出结点的遍历序列; 3. 求二叉树的深度/结点数目/叶结点数目;(选做) 4. 将二叉树每个结点的左右子树交换位置。(选做)