假设你是一名c++程序员,请帮我写一段c++代码来实现以下功能: (1)对于任意给出的前缀表达式(不带括号)、中缀表达式(可以带括号)或后缀表达式(不带括号),能够在计算机内部构造出一棵表达式二叉树,并且以图示显示出来(字符图或图形的形式)。 (2)对于构造好的内部表达式二叉树,按照用户的要求,输出相应的前缀表达式(不带括号)、中缀表达式(可以带括号,但不允许冗余括号)或后缀表达式(不带括号)。
时间: 2023-06-06 08:04:57 浏览: 100
代码如下:
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
//定义二叉树结构体
typedef struct TreeNode {
char data;
struct TreeNode* left;
struct TreeNode* right;
} TreeNode;
//定义栈结构体
typedef struct Stack {
int top;
TreeNode** data;
int size;
} Stack;
//初始化栈
void initStack(Stack* s, int size) {
s->top = -1;
s->size = size;
s->data = (TreeNode**)malloc(sizeof(TreeNode*) * size);
}
//判断栈是否为空
int isEmpty(Stack* s) {
return s->top == -1;
}
//判断栈是否已满
int isFull(Stack* s) {
return s->top == s->size - 1;
}
//入栈操作
void push(Stack* s, TreeNode* elem) {
if (isFull(s)) {
return;
}
s->data[++s->top] = elem;
}
//出栈操作
TreeNode* pop(Stack* s) {
if (isEmpty(s)) {
return NULL;
}
return s->data[s->top--];
}
//获取栈顶元素
TreeNode* getTop(Stack* s) {
if (isEmpty(s)) {
return NULL;
}
return s->data[s->top];
}
//判断字符是否为运算符
int isOperator(char c) {
return c == '+' || c == '-' || c == '*' || c == '/';
}
//创建新结点
TreeNode* createNode(char data) {
TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
node->data = data;
node->left = NULL;
node->right = NULL;
return node;
}
//构造表达式树
TreeNode* buildExpressionTree(char* exp) {
Stack s;
initStack(&s, 100);
TreeNode* root = NULL;
int i = 0;
while (exp[i] != '\0') {
if (isdigit(exp[i])) {
//创建叶子结点
TreeNode* node = createNode(exp[i]);
push(&s, node);
}
else if (isOperator(exp[i])) {
//创建父结点
TreeNode* node = createNode(exp[i]);
if (root == NULL) {
root = node;
}
else {
TreeNode* right = pop(&s);
TreeNode* left = pop(&s);
node->left = left;
node->right = right;
}
push(&s, node);
}
i++;
}
return root;
}
//前序遍历表达式树并打印结果
void preorder(TreeNode* node) {
if (node) {
printf("%c", node->data);
preorder(node->left);
preorder(node->right);
}
}
//中序遍历表达式树并打印结果
void inorder(TreeNode* node) {
if (node) {
if (isOperator(node->data)) {
printf("(");
}
inorder(node->left);
printf("%c", node->data);
inorder(node->right);
if (isOperator(node->data)) {
printf(")");
}
}
}
//后序遍历表达式树并打印结果
void postorder(TreeNode* node) {
if (node) {
postorder(node->left);
postorder(node->right);
printf("%c", node->data);
}
}
int main() {
char exp[] = "3+4*5";
TreeNode* root = buildExpressionTree(exp);
printf("表达式树:\n");
printf(" %c\n", root->data);
printf(" / \\\n");
printf(" %c %c\n", root->left->data, root->right->data);
printf(" / \\ / \\\n");
printf(" %c %c %c %c\n", root->left->left->data, root->left->right->data, root->right->left->data, root->right->right->data);
printf("前缀表达式:");
preorder(root);
printf("\n");
printf("中缀表达式:");
inorder(root);
printf("\n");
printf("后缀表达式:");
postorder(root);
printf("\n");
return 0;
}
阅读全文