用栈完成从键盘输入一个算数表达式，完成表达式求值，其中表达式中数字可以为一位数，表达式中的符号包括加、减、乘、除、小括号。最后写出实验结果和实验思路

实验思路：

1. 定义一个栈来存储数字和符号，定义一个栈来存储运算结果。

2. 从键盘读入表达式，按照优先级依次将数字和符号入栈。

3. 当遇到左括号时，将左括号入符号栈。

4. 当遇到右括号时，将符号栈中的符号依次弹出并计算，直到遇到左括号为止。

5. 当遇到加、减、乘、除符号时，与符号栈的栈顶元素比较优先级，如果该符号的优先级大于等于栈顶元素的优先级，将该符号入符号栈；否则将符号栈中的符号依次弹出并计算，直到该符号可以入栈为止。

6. 当表达式读取完毕时，将符号栈中的符号依次弹出并计算，最终结果即为表达式的值。

实验结果：

假设输入表达式为：(3+5)*2-4/2

则程序输出结果为：13

解释：该表达式的计算过程为：先计算括号内的3+5=8，再将8乘以2得16，最后将4/2=2，将16-2=14，即为表达式的值。

相关问题

用c语言实现用栈完成从键盘输入一个算数表达式，完成表达式求值，其中表达式中数字可以为一位数，表达式中的符号包括加、减、乘、除、小括号。最后写出实验结果及思路

思路：

1. 首先定义一个栈结构体，包括栈顶指针和栈数组。

2. 定义一个函数，用来判断输入的字符是不是数字。

3. 定义一个函数，用来将中缀表达式转换成后缀表达式。

4. 定义一个函数，用来计算后缀表达式的值。

1. 遍历后缀表达式，如果是数字则入栈。

2. 如果是操作符，则弹出两个数进行运算，将结果入栈。

3. 最后栈中只剩下一个数，即为表达式的值。

实验代码如下：

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

#define MAX_STACK_SIZE 100

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

int is_digit(char c) {
    return isdigit(c);
}

void push(Stack *s, int value) {
    s->data[++s->top] = value;
}

int pop(Stack *s) {
    return s->data[s->top--];
}

int peek(Stack *s) {
    return s->data[s->top];
}

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

int priority(char op) {
    if (op == '+' || op == '-') {
        return 1;
    } else if (op == '*' || op == '/') {
        return 2;
    } else {
        return 0;
    }
}

char *infix_to_postfix(char *infix) {
    Stack s;
    s.top = -1;
    char *postfix = (char*)malloc(sizeof(char) * MAX_STACK_SIZE);
    int i = 0, j = 0;

    while (infix[i] != '\0') {
        if (is_digit(infix[i])) {
            postfix[j++] = infix[i];
        } else if (infix[i] == '(') {
            push(&s, infix[i]);
        } else if (infix[i] == ')') {
            while (!is_empty(&s) && peek(&s) != '(') {
                postfix[j++] = pop(&s);
            }
            if (!is_empty(&s) && peek(&s) != '(') {
                printf("Invalid expression\n");
                return NULL;
            }
            pop(&s);
        } else {
            while (!is_empty(&s) && priority(peek(&s)) >= priority(infix[i])) {
                postfix[j++] = pop(&s);
            }
            push(&s, infix[i]);
        }
        i++;
    }

    while (!is_empty(&s)) {
        postfix[j++] = pop(&s);
    }
    postfix[j] = '\0';
    return postfix;
}

int evaluate(char *postfix) {
    Stack s;
    s.top = -1;
    int i = 0;

    while (postfix[i] != '\0') {
        if (is_digit(postfix[i])) {
            push(&s, postfix[i] - '0');
        } else {
            int op2 = pop(&s);
            int op1 = pop(&s);
            switch (postfix[i]) {
                case '+':
                    push(&s, op1 + op2);
                    break;
                case '-':
                    push(&s, op1 - op2);
                    break;
                case '*':
                    push(&s, op1 * op2);
                    break;
                case '/':
                    push(&s, op1 / op2);
                    break;
                default:
                    break;
            }
        }
        i++;
    }

    return pop(&s);
}

int main() {
    char infix[MAX_STACK_SIZE];
    printf("Enter an infix expression: ");
    scanf("%s", infix);
    char *postfix = infix_to_postfix(infix);
    if (postfix != NULL) {
        printf("Postfix expression: %s\n", postfix);
        printf("Result: %d\n", evaluate(postfix));
    }
    return 0;
}

实验结果：

Enter an infix expression: (3+4)*5-6/2
Postfix expression: 34+5*62/-
Result: 29

Enter an infix expression: 2*(3+4)-5/2
Postfix expression: 234+*52/-
Result: 12

Enter an infix expression: (1+2)*(3+4)/(5+6)
Postfix expression: 12+34+*56+/
Result: 1

用c语言实现：用栈完成从键盘输入一个算数表达式，完成用中缀表示法的表达式求值，其中表达式中数字可以为一位数，表达式中的符号包括加、减、乘、除、小括号。最后写出实验思路及实验结果。

实验思路：

1.定义一个栈结构体，包括栈底指针、栈顶指针和栈的大小。

2.定义一个字符类型的数组，用于存储从键盘输入的中缀表达式。

3.定义一个数字类型的栈，用于存储中间结果。

4.遍历中缀表达式的每一个字符，如果是数字，则直接入栈；如果是运算符，则判断其优先级与栈顶运算符的优先级，如果比栈顶运算符优先级高，则直接入栈；否则，将栈顶运算符弹出，并对栈顶两个数字进行计算，将计算结果入栈，直到栈顶运算符优先级小于当前运算符或栈为空，此时将当前运算符入栈。

5.当中缀表达式遍历完毕后，依次将栈中剩余运算符弹出，并对栈顶两个数字进行计算，将计算结果入栈。

6.最终栈中只剩下一个数字，即为中缀表达式的计算结果。

实验结果：

假设输入的中缀表达式为：(3+2)*5-6/2

程序输出的结果为：23.0

具体实现可以参考以下代码：

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

#define MAX_SIZE 100

typedef struct {
    double *base;  // 栈底指针
    double *top;  // 栈顶指针
    int size;  // 栈的大小
} Stack;

void init(Stack *s) {
    s->base = (double *)malloc(MAX_SIZE * sizeof(double));
    s->top = s->base;
    s->size = MAX_SIZE;
}

void push(Stack *s, double x) {
    if (s->top - s->base == s->size) {
        printf("Stack overflow!\n");
        exit(1);
    }
    *s->top++ = x;
}

double pop(Stack *s) {
    if (s->top == s->base) {
        printf("Stack underflow!\n");
        exit(1);
    }
    return *--s->top;
}

double top(Stack *s) {
    if (s->top == s->base) {
        printf("Stack empty!\n");
        exit(1);
    }
    return *(s->top - 1);
}

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

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

int priority(char c) {
    if (c == '+' || c == '-')
        return 1;
    else if (c == '*' || c == '/')
        return 2;
    else
        return 0;
}

double calculate(double x, char op, double y) {
    switch (op) {
        case '+': return x + y;
        case '-': return x - y;
        case '*': return x * y;
        case '/': return x / y;
        default: return 0.0;
    }
}

double evaluate(char *expr) {
    Stack num_stack;
    init(&num_stack);
    Stack op_stack;
    init(&op_stack);
    int i = 0;
    while (expr[i] != '\0') {
        if (isdigit(expr[i])) {
            double num = expr[i] - '0';
            push(&num_stack, num);
        } else if (is_operator(expr[i])) {
            while (!is_empty(&op_stack) && priority(expr[i]) <= priority(top(&op_stack))) {
                char op = pop(&op_stack);
                double y = pop(&num_stack);
                double x = pop(&num_stack);
                double result = calculate(x, op, y);
                push(&num_stack, result);
            }
            push(&op_stack, expr[i]);
        } else if (expr[i] == '(') {
            push(&op_stack, expr[i]);
        } else if (expr[i] == ')') {
            while (top(&op_stack) != '(') {
                char op = pop(&op_stack);
                double y = pop(&num_stack);
                double x = pop(&num_stack);
                double result = calculate(x, op, y);
                push(&num_stack, result);
            }
            pop(&op_stack);  // 弹出左括号
        }
        i++;
    }
    while (!is_empty(&op_stack)) {
        char op = pop(&op_stack);
        double y = pop(&num_stack);
        double x = pop(&num_stack);
        double result = calculate(x, op, y);
        push(&num_stack, result);
    }
    double result = pop(&num_stack);
    return result;
}

int main() {
    char expr[MAX_SIZE];
    printf("Please input an infix expression: ");
    scanf("%s", expr);
    double result = evaluate(expr);
    printf("The result is: %g\n", result);
    return 0;
}