求利用c\c++将字符串集构建成一棵树的程序代码

发布网友发布时间：2022-10-17 23:26

共1个回答

热心网友时间：2023-11-04 16:43

表达式树是树结构的一个经典应用。

常见的表达式：3+5*7+2为中缀表达式。

这里，我实现一种转换算法，那就是先把中缀式子转化为一棵树，然后使用不同的遍历遍历方式得到不同的表达式

【注】（仅仅给出没有括号时的代码，为了简化字符串处理，我没有使用字符串，而是使用了字符，因此不支持两位的数字算式）

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct string_node {
char tag; //定义字符
struct string_node *left;
struct string_node *right;
struct string_node *parent;
};
struct string_node *gen_sub_tree(char*str, int len)
{
struct string_node *root;
int i = 0;
for (i = 0; i < len; i++) {
struct string_node *node = (struct string_node*)calloc(1, sizeof(structstring_node));
node->tag =str[i];
if(isdigit(str[i])) {
if (i != 0) {//运算由左至右，除了第一个操作数，其它全部为右操作数，高优先级的会处在树的旁支
root->right = node;
node->parent = root;
}
root = node;
} else if((str[i] == 'x') || (str[i] == '/')) {
//处理乘除运算符
struct string_node *temp_root = NULL, *temp_parent = NULL;
if (root->parent &&(root->parent->tag == '+' || root->parent->tag == '-')) {
temp_parent = root->parent;
temp_root = root;
} else if(root->parent) {
temp_parent =root->parent->parent;
temp_root = root->parent;
} else {
temp_root = root;
}
node->parent = temp_parent;
if (temp_parent)
temp_parent->right = node;
node->left = temp_root;
temp_root->parent = node;
root = node;
} else if (str[i] == '+' || str[i] == '-') {
//处理加减运算符
struct string_node *temp_root =NULL, *temp_parent = NULL;
if (root->parent &&root->parent->parent &&(root->parent->tag == 'x' || root->parent->tag == '/')) {
temp_root =root->parent->parent;
} else if (root->parent&& !root->parent->parent){
temp_root = root->parent;
} else {
temp_root = root;
}
node->left = temp_root;
temp_root->parent = node;
root = node;
}
}
//找到树根，返回调用者
while (root->parent) {
root = root->parent;
}
return root;
}
int main(int argc, char **argv)
{
struct string_node *root;
char str[40] ={'1','+','0','+','2','x','5','+','3','x','4','x','2', '-', '7'};
root = NULL;
root = gen_sub_tree(str, 100);
print_result(root);
return 0;
}
//输出结果
void print_result(struct string_node*p)
{
if(p != NULL) {
//此为后缀表达式，根据printf的位置不同可以得到不同的X缀表达式
print_result(p->left);
print_result(p->right);
printf("%c\n", p->tag);
}
}

【】下面考虑加上括号时的情况，由于号优先级最高，而且还不是像运算符那样结合操作数的字符，因此把括号括住的成分单独作为一个操作数比较好，这样就可以递归的实现了。，只需要加入对’(‘和’)’的解析即可喽，递归调用gen_sub_tree即可。以下为加入括号处理的代码：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct string_node {
char tag; //定义字符
struct string_node *left;
struct string_node *right;
struct string_node *parent;
};
struct string_node *gen_sub_tree(char*str, int len)
{
struct string_node *root;
int i = 0;
for (i = 0; i < len; i++) {
struct string_node *node = (struct string_node*)calloc(1, sizeof(structstring_node));
node->tag =str[i];
if(isdigit(str[i])) {
if (i != 0) {//运算由左至右，除了第一个操作数，其它全部为右操作数，高优先级的会处在树的旁支
root->right = node;
node->parent = root;
}
root = node;
} else if((str[i] == 'x') || (str[i] == '/')) {
//处理乘除运算符
struct string_node *temp_root = NULL, *temp_parent = NULL;
if (root->parent &&(root->parent->tag == '+' || root->parent->tag == '-')) {
temp_parent = root->parent;
temp_root = root;
} else if(root->parent) {
temp_parent =root->parent->parent;
temp_root = root->parent;
} else {
temp_root = root;
}
node->parent = temp_parent;
if (temp_parent)
temp_parent->right = node;
node->left = temp_root;
temp_root->parent = node;
root = node;
} else if (str[i] == '+' || str[i] == '-') {
//处理加减运算符
struct string_node *temp_root =NULL, *temp_parent = NULL;
if (root->parent &&root->parent->parent &&(root->parent->tag == 'x' || root->parent->tag == '/')) {
temp_root =root->parent->parent;
} else if (root->parent&& !root->parent->parent){
temp_root = root->parent;
} else {
temp_root = root;
}
node->left = temp_root;
temp_root->parent = node;
root = node;
}
}
//找到树根，返回调用者
while (root->parent) {
root = root->parent;
}
return root;
}
int main(int argc, char **argv)
{
struct string_node *root;
char str[40] ={'1','+','0','+','2','x','5','+','3','x','4','x','2', '-', '7'};
root = NULL;
root = gen_sub_tree(str, 100);
print_result(root);
return 0;
}
//输出结果
void print_result(struct string_node*p)
{
if(p != NULL) {
//此为后缀表达式，根据printf的位置不同可以得到不同的X缀表达式
print_result(p->left);
print_result(p->right);
printf("%c\n", p->tag);
}
}