后缀表达式转为树,后缀表达式中含有大于十的数,用c语言写出代码
时间: 2023-10-23 19:15:55 浏览: 76
用树的形式来实现表达式的前中后缀转换
以下是用C语言实现将后缀表达式转化为表达式树的示例代码:
```c
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#define MAX_STACK_SIZE 100
typedef struct TreeNode {
char data;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode, *TreeNodePtr;
typedef struct Stack {
int top;
TreeNodePtr stackArray[MAX_STACK_SIZE];
} Stack, *StackPtr;
void push(StackPtr stack, TreeNodePtr node) {
if (stack->top < MAX_STACK_SIZE - 1) {
stack->stackArray[++stack->top] = node;
} else {
printf("Stack overflow\n");
exit(1);
}
}
TreeNodePtr pop(StackPtr stack) {
if (stack->top > -1) {
return stack->stackArray[stack->top--];
} else {
printf("Stack underflow\n");
exit(1);
}
}
int isOperator(char c) {
return (c == '+' || c == '-' || c == '*' || c == '/');
}
TreeNodePtr createNode(char data) {
TreeNodePtr node = (TreeNodePtr) malloc(sizeof(TreeNode));
node->data = data;
node->left = node->right = NULL;
return node;
}
TreeNodePtr createExpressionTree(char *postfix) {
Stack stack;
stack.top = -1;
int i = 0;
char c = postfix[i];
while (c != '\0') {
if (!isOperator(c) && !isdigit(c)) {
printf("Invalid character in postfix expression\n");
exit(1);
}
TreeNodePtr node = createNode(c);
if (isdigit(c)) {
push(&stack, node);
} else {
node->right = pop(&stack);
node->left = pop(&stack);
push(&stack, node);
}
c = postfix[++i];
}
return pop(&stack);
}
void inorderTraversal(TreeNodePtr root) {
if (root) {
inorderTraversal(root->left);
printf("%c ", root->data);
inorderTraversal(root->right);
}
}
int main() {
char postfix[] = "23+45*6/+";
TreeNodePtr root = createExpressionTree(postfix);
printf("Inorder traversal of expression tree: ");
inorderTraversal(root);
printf("\n");
return 0;
}
```
该程序中使用了一个栈来存储表达式树的节点,其中`push`和`pop`函数用于将节点压入栈中和从栈中弹出节点。`isOperator`函数用于检查给定字符是否为运算符。`createNode`函数用于创建新的节点。`createExpressionTree`函数用于从给定的后缀表达式中创建表达式树。最后,`inorderTraversal`函数用于对表达式树进行中序遍历并输出结果。
阅读全文