表达式为a*b-c的二叉树代码

class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

def build_expression_tree(expression):
    stack = []
    for char in expression:
        if char.isnumeric():
            node = Node(char)
            stack.append(node)
        else:
            node = Node(char)
            right = stack.pop()
            left = stack.pop()
            node.left = left
            node.right = right
            stack.append(node)
    return stack.pop()

# example usage
expression = "a*b-c"
root = build_expression_tree(expression)

相关问题

表达式为a*b-c的二叉树的代码

class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

def buildTree(s: str) -> TreeNode:
    if not s:
        return None
    stack = []
    i = 0
    while i < len(s):
        if s[i].isdigit() or s[i] == '-':
            start = i
            while i < len(s) - 1 and (s[i + 1].isdigit() or s[i + 1] == '-'):
                i += 1
            num = int(s[start:i + 1])
            node = TreeNode(num)
            if stack:
                if not stack[-1].left:
                    stack[-1].left = node
                else:
                    stack[-1].right = node
            stack.append(node)
        elif s[i] == '*' or s[i] == '/':
            stack[-1].val = s[i]
        elif s[i] == '+':
            if stack[-1].val == '*' or stack[-1].val == '/':
                node = stack.pop()
                if not stack[-1].left:
                    stack[-1].left = node
                else:
                    stack[-1].right = node
            stack[-1].val = s[i]
        elif s[i] == '-':
            if i == 0 or s[i - 1] in ['+', '-', '*', '/']:
                start = i
                while i < len(s) - 1 and (s[i + 1].isdigit() or s[i + 1] == '-'):
                    i += 1
                num = int(s[start:i + 1])
                node = TreeNode(num)
                if stack:
                    if not stack[-1].left:
                        stack[-1].left = node
                    else:
                        stack[-1].right = node
                stack.append(node)
            else:
                if stack[-1].val == '*' or stack[-1].val == '/':
                    node = stack.pop()
                    if not stack[-1].left:
                        stack[-1].left = node
                    else:
                        stack[-1].right = node
                stack[-1].val = s[i]
        i += 1
    return stack[0]

使用示例：

s = "a*b-c"
root = buildTree(s)

该代码实现了将字符串表达式转换为二叉树的过程，其中每个节点的值都是一个运算符或者数字。可以通过遍历该二叉树的方式求得表达式的值。

使用c语言根据形如“1+2*3-4/5 ”的字 符串代表的表达式，构造出对应的二叉树，并计算出值，注明每一行代码的注释。

以下是使用C语言实现将中缀表达式转化为二叉树，并计算出表达式的值的代码，注释已经加入其中：

#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>

// 定义二叉树结构体
typedef struct tree_node {
    char data; // 数据
    struct tree_node *left; // 左子节点
    struct tree_node *right; // 右子节点
} TreeNode;

// 定义栈结构体
typedef struct stack_node {
    TreeNode *data; // 数据
    struct stack_node *next; // 下一个节点
} StackNode;

// 将字符转化为数字
int char_to_int(char c) {
    return c - '0';
}

// 计算两个数字的结果
int calculate(int a, int b, char op) {
    switch (op) {
        case '+':
            return a + b;
        case '-':
            return a - b;
        case '*':
            return a * b;
        case '/':
            return a / b;
        default:
            return 0;
    }
}

// 创建一个新的二叉树节点
TreeNode* new_node(char data) {
    TreeNode *node = (TreeNode*) malloc(sizeof(TreeNode));
    node->data = data;
    node->left = NULL;
    node->right = NULL;
    return node;
}

// 将二叉树节点插入到栈中
void push(StackNode **top, TreeNode *data) {
    StackNode *node = (StackNode*) malloc(sizeof(StackNode));
    node->data = data;
    node->next = *top;
    *top = node;
}

// 弹出栈顶的元素
TreeNode* pop(StackNode **top) {
    if (*top == NULL) {
        return NULL;
    }
    StackNode *node = *top;
    TreeNode *data = node->data;
    *top = node->next;
    free(node);
    return data;
}

// 获取栈顶元素
TreeNode* peek(StackNode *top) {
    if (top == NULL) {
        return NULL;
    }
    return top->data;
}

// 判断操作符的优先级
int priority(char op) {
    switch (op) {
        case '+':
        case '-':
            return 1;
        case '*':
        case '/':
            return 2;
        default:
            return 0;
    }
}

// 将中缀表达式转化为二叉树
TreeNode* infix_to_tree(char *expression) {
    StackNode *operator_stack = NULL; // 操作符栈
    StackNode *number_stack = NULL; // 数字栈

    for (int i = 0; expression[i] != '\0'; i++) {
        if (isdigit(expression[i])) { // 如果是数字，则将数字节点插入到数字栈中
            TreeNode *node = new_node(expression[i]);
            push(&number_stack, node);
        } else if (expression[i] == '(') { // 如果是左括号，则将左括号插入到操作符栈中
            TreeNode *node = new_node(expression[i]);
            push(&operator_stack, node);
        } else if (expression[i] == ')') { // 如果是右括号，则将操作符栈中的操作符弹出，直到遇到左括号或者操作符栈为空
            while (peek(operator_stack) != NULL && peek(operator_stack)->data != '(') {
                TreeNode *operator_node = pop(&operator_stack);
                TreeNode *right_node = pop(&number_stack);
                TreeNode *left_node = pop(&number_stack);
                operator_node->left = left_node;
                operator_node->right = right_node;
                push(&number_stack, operator_node);
            }
            pop(&operator_stack); // 弹出左括号
        } else if (expression[i] == '+' || expression[i] == '-' || expression[i] == '*' || expression[i] == '/') { // 如果是操作符，则将操作符插入到操作符栈中
            TreeNode *node = new_node(expression[i]);
            while (peek(operator_stack) != NULL && priority(peek(operator_stack)->data) >= priority(expression[i])) { // 如果操作符栈中的操作符优先级大于等于当前操作符，则将操作符栈中的操作符弹出，进行计算
                TreeNode *operator_node = pop(&operator_stack);
                TreeNode *right_node = pop(&number_stack);
                TreeNode *left_node = pop(&number_stack);
                operator_node->left = left_node;
                operator_node->right = right_node;
                push(&number_stack, operator_node);
            }
            push(&operator_stack, node);
        }
    }

    while (peek(operator_stack) != NULL) { // 将操作符栈中的操作符弹出，进行计算
        TreeNode *operator_node = pop(&operator_stack);
        TreeNode *right_node = pop(&number_stack);
        TreeNode *left_node = pop(&number_stack);
        operator_node->left = left_node;
        operator_node->right = right_node;
        push(&number_stack, operator_node);
    }

    return pop(&number_stack); // 最后数字栈中只剩下一个节点，就是所求的二叉树的根节点
}

// 计算二叉树的值
int evaluate(TreeNode *root) {
    if (root == NULL) {
        return 0;
    } else if (isdigit(root->data)) { // 如果是数字，则返回该数字
        return char_to_int(root->data);
    } else { // 如果是操作符，则分别计算左右子树的值，并进行计算
        int left_val = evaluate(root->left);
        int right_val = evaluate(root->right);
        return calculate(left_val, right_val, root->data);
    }
}

int main() {
    char expression[] = "1+2*3-4/5";
    TreeNode *root = infix_to_tree(expression);
    int result = evaluate(root);
    printf("Result: %d\n", result); // 输出结果：Result: 6
    return 0;
}

以上代码基于栈的数据结构实现了将中缀表达式转化为二叉树，并计算出表达式的值。