数据结构表达式求值c语言程序

数据结构表达式求值c语言程序是一种用C语言编写的程序，用于计算数学表达式的值。该程序使用栈的数据结构来实现表达式求值，可以处理包括加、减、乘、除、括号等在内的各种运算符和操作数。用户只需输入表达式，程序即可自动计算出结果。该程序的实现需要掌握栈的基本操作和中缀表达式转后缀表达式的算法。如果您对数据结构和算法有一定的了解，可以尝试编写一个类似的程序来实现表达式求值。

相关问题

数据结构栈的算术表达式求值C语言

栈是一种后进先出（LIFO）的数据结构，它可以用来解决算术表达式求值问题。下面是一个使用栈求解算术表达式的C语言程序：

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

#define MAX_STACK_SIZE 100

typedef struct {
    int top;
    int data[MAX_STACK_SIZE];
} Stack;

void init(Stack *s) {
    s->top = -1;
}

int is_empty(Stack *s) {
    return s->top == -1;
}

int is_full(Stack *s) {
    return s->top == MAX_STACK_SIZE - 1;
}

void push(Stack *s, int x) {
    if (is_full(s)) {
        printf("Stack overflow\n");
        exit(1);
    }
    s->data[++s->top] = x;
}

int pop(Stack *s) {
    if (is_empty(s)) {
        printf("Stack underflow\n");
        exit(1);
    }
    return s->data[s->top--];
}

int peek(Stack *s) {
    if (is_empty(s)) {
        printf("Stack underflow\n");
        exit(1);
    }
    return s->data[s->top];
}

int evaluate(char *expr) {
    Stack operand_stack;
    Stack operator_stack;
    init(&operand_stack);
    init(&operator_stack);

    while (*expr != '\0') {
        if (isdigit(*expr)) {
            int value = 0;
            while (isdigit(*expr)) {
                value = value * 10 + (*expr - '0');
                expr++;
            }
            push(&operand_stack, value);
        } else if (*expr == '(') {
            push(&operator_stack, *expr);
            expr++;
        } else if (*expr == ')') {
            while (peek(&operator_stack) != '(') {
                int op2 = pop(&operand_stack);
                int op1 = pop(&operand_stack);
                char op = pop(&operator_stack);
                int result;
                switch (op) {
                    case '+': result = op1 + op2; break;
                    case '-': result = op1 - op2; break;
                    case '*': result = op1 * op2; break;
                    case '/': result = op1 / op2; break;
                }
                push(&operand_stack, result);
            }
            pop(&operator_stack);
            expr++;
        } else if (*expr == '+' || *expr == '-' || *expr == '*' || *expr == '/') {
            while (!is_empty(&operator_stack) && peek(&operator_stack) != '(' && ((*expr == '+' || *expr == '-') && (peek(&operator_stack) == '*' || peek(&operator_stack) == '/'))) {
                int op2 = pop(&operand_stack);
                int op1 = pop(&operand_stack);
                char op = pop(&operator_stack);
                int result;
                switch (op) {
                    case '+': result = op1 + op2; break;
                    case '-': result = op1 - op2; break;
                    case '*': result = op1 * op2; break;
                    case '/': result = op1 / op2; break;
                }
                push(&operand_stack, result);
            }
            push(&operator_stack, *expr);
            expr++;
        } else {
            printf("Invalid character: %c\n", *expr);
            exit(1);
        }
    }

    while (!is_empty(&operator_stack)) {
        int op2 = pop(&operand_stack);
        int op1 = pop(&operand_stack);
        char op = pop(&operator_stack);
        int result;
        switch (op) {
            case '+': result = op1 + op2; break;
            case '-': result = op1 - op2; break;
            case '*': result = op1 * op2; break;
            case '/': result = op1 / op2; break;
        }
        push(&operand_stack, result);
    }

    return pop(&operand_stack);
}

int main() {
    char expr[100];
    printf("Enter an arithmetic expression: ");
    scanf("%s", expr);
    int result = evaluate(expr);
    printf("Result: %d\n", result);
    return 0;
}

该程序使用两个栈，一个用于存储操作数，另一个用于存储运算符。它遍历算术表达式中的每个字符，并根据字符的类型执行相应的操作。如果字符是数字，则将其转换为整数并将其推入操作数栈中；如果字符是左括号，则将其推入运算符栈中；如果字符是右括号，则从运算符栈中弹出运算符和操作数，执行相应的运算，并将结果推入操作数栈中，直到遇到左括号；如果字符是加、减、乘或除号，则从运算符栈中弹出运算符和操作数，执行相应的运算，并将结果推入操作数栈中，直到运算符栈为空或栈顶运算符的优先级低于当前运算符的优先级。最后，操作数栈中剩下的唯一元素就是算术表达式的值。

数据结构中表达式求值用c语言写出来

以下是一个简单的表达式求值程序的C语言代码，它可以处理加、减、乘、除和括号：

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

#define MAX_STACK_SIZE 100

typedef struct {
    int top;
    double data[MAX_STACK_SIZE];
} Stack;

void push(Stack *s, double value) {
    if (s->top == MAX_STACK_SIZE - 1) {
        fprintf(stderr, "Stack overflow\n");
        exit(EXIT_FAILURE);
    }
    s->data[++s->top] = value;
}

double pop(Stack *s) {
    if (s->top == -1) {
        fprintf(stderr, "Stack underflow\n");
        exit(EXIT_FAILURE);
    }
    return s->data[s->top--];
}

int is_operator(char c) {
    return c == '+' || c == '-' || c == '*' || c == '/';
}

double eval(char *expression) {
    Stack operand_stack;
    operand_stack.top = -1;

    Stack operator_stack;
    operator_stack.top = -1;

    char *p = expression;

    while (*p != '\0') {
        if (isdigit(*p)) {
            double value = *p - '0';
            while (isdigit(*(++p))) {
                value = value * 10 + *p - '0';
            }
            push(&operand_stack, value);
        } else if (is_operator(*p)) {
            while (operator_stack.top != -1 && is_operator(operator_stack.data[operator_stack.top]) &&
                   ((*p == '*' || *p == '/') || (*p == '+' || *p == '-') &&
                    (operator_stack.data[operator_stack.top] == '*' || operator_stack.data[operator_stack.top] == '/'))) {
                double operand2 = pop(&operand_stack);
                double operand1 = pop(&operand_stack);
                char operator = pop(&operator_stack);

                switch (operator) {
                    case '+':
                        push(&operand_stack, operand1 + operand2);
                        break;
                    case '-':
                        push(&operand_stack, operand1 - operand2);
                        break;
                    case '*':
                        push(&operand_stack, operand1 * operand2);
                        break;
                    case '/':
                        push(&operand_stack, operand1 / operand2);
                        break;
                }
            }
            push(&operator_stack, *p);
            p++;
        } else if (*p == '(') {
            push(&operator_stack, '(');
            p++;
        } else if (*p == ')') {
            while (operator_stack.top != -1 && operator_stack.data[operator_stack.top] != '(') {
                double operand2 = pop(&operand_stack);
                double operand1 = pop(&operand_stack);
                char operator = pop(&operator_stack);

                switch (operator) {
                    case '+':
                        push(&operand_stack, operand1 + operand2);
                        break;
                    case '-':
                        push(&operand_stack, operand1 - operand2);
                        break;
                    case '*':
                        push(&operand_stack, operand1 * operand2);
                        break;
                    case '/':
                        push(&operand_stack, operand1 / operand2);
                        break;
                }
            }
            if (operator_stack.top == -1) {
                fprintf(stderr, "Unmatched parenthesis\n");
                exit(EXIT_FAILURE);
            }
            pop(&operator_stack);
            p++;
        } else {
            fprintf(stderr, "Invalid character: %c\n", *p);
            exit(EXIT_FAILURE);
        }
    }

    while (operator_stack.top != -1) {
        double operand2 = pop(&operand_stack);
        double operand1 = pop(&operand_stack);
        char operator = pop(&operator_stack);

        switch (operator) {
            case '+':
                push(&operand_stack, operand1 + operand2);
                break;
            case '-':
                push(&operand_stack, operand1 - operand2);
                break;
            case '*':
                push(&operand_stack, operand1 * operand2);
                break;
            case '/':
                push(&operand_stack, operand1 / operand2);
                break;
        }
    }

    if (operand_stack.top != 0) {
        fprintf(stderr, "Invalid expression\n");
        exit(EXIT_FAILURE);
    }

    return pop(&operand_stack);
}

int main() {
    char expression[100];
    printf("Enter an expression: ");
    scanf("%s", expression);
    double result = eval(expression);
    printf("Result: %g\n", result);
    return 0;
}

该程序使用两个栈来实现表达式求值：一个操作数栈和一个操作符栈。它首先扫描表达式，将操作数压入操作数栈，将操作符压入操作符栈。当它遇到右括号时，它从操作数栈中弹出两个操作数，从操作符栈中弹出一个操作符，并将它们组合成一个新的操作数，然后将新操作数压入操作数栈中。当它遇到左括号时，只需将左括号压入操作符栈中。当它遇到一个普通的操作符时，它将从操作数栈中弹出两个操作数，从操作符栈中弹出一个操作符，并将它们组合成一个新的操作数，然后将新操作数压入操作数栈中。

它使用了一个双重循环来处理优先级，因为乘法和除法优先级高于加法和减法。当在操作符栈中发现一个优先级更高的操作符时，它将从操作数栈中弹出两个操作数，从操作符栈中弹出一个操作符，并将它们组合成一个新的操作数，然后将新操作数压入操作数栈中。循环会一直进行，直到操作符栈为空或遇到一个优先级较低的操作符。

最后，当操作符栈为空时，它将从操作数栈中弹出两个操作数，从操作符栈中弹出一个操作符，并将它们组合成一个新的操作数，然后将新操作数压入操作数栈中。在这一点上，操作数栈应该只剩下一个元素，这就是表达式的值。如果操作数栈中还有其他元素，或者在处理括号时遇到了不匹配的括号，则程序将输出错误消息并退出。