C语言 3. 数据结构和ACM2023-第三章-四则运算表达式的运算 - LJD 一、实验目的 (1) 熟悉C/C++基本编程,培养动手能力； (2) 复习顺序表的初始化，建立和查找； (3) 掌握栈顺序存储结构定义及基本操作。 二、实验内容 编程实现四则运算表达式的运算。 输入说明：通过控制台输入四则运算表达式，表达式不超过40个字符，以“=”作为结束符，例如：3 + 2 *（5+2）=。 输入假设：所有操作数均为正数。 输出说明：计算结果从控制台输出给用户，结果精确到小数点后2位。或者输出错误ERROR。 1、创建运算符优先级静态表，并实现运算符优先级查找函数Precede(x, y)。参数x，y是四则运算符，包括+、－、*、\、(、)、=。 2、应用Precede()函数，编写程序计算中缀表达式（一般表达式）的值。

以下是C语言代码实现：

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

#define MAXSIZE 100 // 栈的最大容量

typedef char ElemType; // 栈存储的元素类型为字符

// 定义顺序栈结构体
typedef struct {
    ElemType data[MAXSIZE]; // 存储栈元素的数组
    int top; // 栈顶指针
} SqStack;

// 初始化顺序栈
void InitStack(SqStack *S) {
    S->top = -1;
}

// 判断栈是否为空
int StackEmpty(SqStack S) {
    return (S.top == -1);
}

// 判断栈是否已满
int StackFull(SqStack S) {
    return (S.top == MAXSIZE - 1);
}

// 进栈
int Push(SqStack *S, ElemType e) {
    if (StackFull(*S)) { // 栈已满，无法进栈
        return 0;
    }
    S->top++;
    S->data[S->top] = e;
    return 1;
}

// 出栈
int Pop(SqStack *S, ElemType *e) {
    if (StackEmpty(*S)) { // 栈已空，无法出栈
        return 0;
    }
    *e = S->data[S->top];
    S->top--;
    return 1;
}

// 获取栈顶元素
int GetTop(SqStack S, ElemType *e) {
    if (StackEmpty(S)) { // 栈已空，无法获取栈顶元素
        return 0;
    }
    *e = S.data[S.top];
    return 1;
}

// 比较运算符优先级
int Precede(ElemType x, ElemType y) {
    int i, j;
    char pri[7][7] = { // 运算符优先级静态表
        {'>', '>', '<', '<', '<', '>', '>'},
        {'>', '>', '<', '<', '<', '>', '>'},
        {'>', '>', '>', '>', '<', '>', '>'},
        {'>', '>', '>', '>', '<', '>', '>'},
        {'<', '<', '<', '<', '<', '=', ' '},
        {'>', '>', '>', '>', ' ', '>', '>'},
        {'<', '<', '<', '<', '<', ' ', '='}
    };
    switch (x) {
        case '+': i = 0; break;
        case '-': i = 1; break;
        case '*': i = 2; break;
        case '/': i = 3; break;
        case '(': i = 4; break;
        case ')': i = 5; break;
        case '=': i = 6; break;
        default: i = 7; break;
    }
    switch (y) {
        case '+': j = 0; break;
        case '-': j = 1; break;
        case '*': j = 2; break;
        case '/': j = 3; break;
        case '(': j = 4; break;
        case ')': j = 5; break;
        case '=': j = 6; break;
        default: j = 7; break;
    }
    return pri[i][j];
}

// 计算两个操作数的结果
double Operate(double a, ElemType theta, double b) {
    double result = 0.0;
    switch (theta) {
        case '+': result = a + b; break;
        case '-': result = a - b; break;
        case '*': result = a * b; break;
        case '/': result = a / b; break;
    }
    return result;
}

// 计算中缀表达式的值
double EvaluateExpression(char *exp) {
    SqStack OPTR, OPND;
    ElemType c, x, theta;
    double a, b, d, e;
    InitStack(&OPTR);
    InitStack(&OPND);
    Push(&OPTR, '='); // 表达式以'='结束
    c = *exp++;
    while (c != '=' || GetTop(OPTR, &x) != '=')
    {
        if (c >= '0' && c <= '9') { // c是操作数，进栈OPND
            d = c - '0';
            while (*exp >= '0' && *exp <= '9') { // 取得操作数的完整数值
                d = d * 10 + (*exp - '0');
                exp++;
            }
            if (*exp == '.') { // 处理小数部分
                exp++;
                e = 0.1;
                while (*exp >= '0' && *exp <= '9') {
                    d += (*exp - '0') * e;
                    e *= 0.1;
                    exp++;
                }
            }
            Push(&OPND, d); // 操作数进栈
            c = *exp++; // 处理下一个字符
        }
        else { // c是运算符
            switch (Precede(x, c)) {
                case '<': // 栈顶运算符优先级低，进栈OPTR
                    Push(&OPTR, c);
                    c = *exp++;
                    break;
                case '=': // 脱括号并接收下一字符
                    Pop(&OPTR, &x);
                    c = *exp++;
                    break;
                case '>': // 退栈并将运算结果进栈OPND
                    Pop(&OPTR, &theta);
                    Pop(&OPND, &b);
                    Pop(&OPND, &a);
                    Push(&OPND, Operate(a, theta, b));
                    break;
            }
        }
    }
    return GetTop(OPND, &a) ? a : 0.0; // 返回最终结果
}

int main() {
    char exp[41];
    printf("Please input an infix expression (with '=' at the end):\n");
    scanf("%s", exp);
    double result = EvaluateExpression(exp);
    if (result == 0.0) {
        printf("ERROR\n");
    }
    else {
        printf("The result is %.2f\n", result);
    }
    return 0;
}

代码中使用了两个顺序栈，一个用于存储运算符，一个用于存储操作数。每次读入一个字符，若为操作数则取完整数值并进栈OPND，若为运算符则与栈顶运算符比较优先级。若栈顶运算符优先级低，则进栈OPTR；若相等，则脱括号并读入下一个字符；若栈顶运算符优先级高，则退栈并将运算结果进栈OPND。最终结果存在OPND栈中，返回栈顶元素即可。

需要注意的是，该代码实现假设所有操作数均为正数，且输入的表达式不超过40个字符。对于负数、小数、超长表达式等情况，还需要进行相应的修改和处理。