难题解答 - 表达式求值

文章摘要

LCY AI Pro

本文围绕“表达式求值”实验题，使用双栈法解析含小数与括号的中缀表达式，给出链式栈实现、运算符优先级处理与保留两位小数输出方案。

原题再现

选自 “ITC - 数据结构A - 第二次实验 - 3.表达式求值”

【问题描述】栈的应用，给定一个以“#”作为结束符的算式，求出算式的结果
【输入形式】以“#”结尾的表达式，运算数为正数。每个表达式占一行。

注：原题中“正数”表述为“正整数”，应有误，已作修改，特此说明。

【输出形式】输出表达式运算的结果。

【样例输入1】4+2.53*3-10/5#
【样例输出1】9.59

【样例输入2】3*(7.91-2)#
【样例输出2】17.73

【样例输入3】2.4*3.6/2#
【样例输出3】4.32

【注意】要处理表达式中带小数的数据，不能仅采用getchar()去接收数据，请注意查阅资料，看看如何处理。
另外，输出数据请保留2位小数。

---

参考代码

#include <bits/stdc++.h>
using namespace std;

struct NumNode {
    double data;
    NumNode* next;
};

struct OpNode {
    char data;
    OpNode* next;
};

void pushNum(NumNode*& s, double x) {
    NumNode* p = new NumNode;
    p->data = x;
    p->next = s;
    s = p;
}

void pushOp(OpNode*& s, char c) {
    OpNode* p = new OpNode;
    p->data = c;
    p->next = s;
    s = p;
}

bool emptyNum(NumNode* s) {
    return s == NULL;
}

bool emptyOp(OpNode* s) {
    return s == NULL;
}

void popNum(NumNode*& s) {
    if (!emptyNum(s)) {
        NumNode* p = s;
        s = s->next;
        delete p;
    }
}

void popOp(OpNode*& s) {
    if (!emptyOp(s)) {
        OpNode* p = s;
        s = s->next;
        delete p;
    }
}

bool topNum(NumNode* s, double& out) {
    if (emptyNum(s)) return false;
    out = s->data;
    return true;
}

bool topOp(OpNode* s, char& out) {
    if (emptyOp(s)) return false;
    out = s->data;
    return true;
}

void clearNum(NumNode*& s) {
    while (!emptyNum(s)) {
        popNum(s);
    }
}

void clearOp(OpNode*& s) {
    while (!emptyOp(s)) {
        popOp(s);
    }
}

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

void applyOnce(NumNode*& nums, OpNode*& ops) {
    double b, a;
    char op;
    if (!topNum(nums, b)) return;
    popNum(nums);

    if (!topNum(nums, a)) return;
    popNum(nums);

    if (!topOp(ops, op)) return;
    popOp(ops);

    if (op == '+') pushNum(nums, a + b);
    else if (op == '-') pushNum(nums, a - b);
    else if (op == '*') pushNum(nums, a * b);
    else if (op == '/') pushNum(nums, a / b);
}

double eval(const string& expr) {
    NumNode* nums = NULL;
    OpNode* ops = NULL;
    for (int i = 0; i < static_cast<int>(expr.length()); ++i) {
        char c = expr[i];
        if (c == ' ') continue;
        if (c == '#') break;
        if (isdigit(c) || c == '.') {
            int j = i;
            while (j < static_cast<int>(expr.length()) && (isdigit(expr[j]) || expr[j] == '.')) {
                j++;
            }
            pushNum(nums, stod(expr.substr(i, j - i)));
            i = j - 1;
        } else if (c == '(') {
            pushOp(ops, c);
        } else if (c == ')') {
            char topc;
            while (topOp(ops, topc) && topc != '(') {
                applyOnce(nums, ops);
            }
            if (topOp(ops, topc) && topc == '(') {
                popOp(ops);
            }
        } else {
            char topc; 
            while (topOp(ops, topc) && topc != '(' && prec(topc) >= prec(c)) {
                applyOnce(nums, ops);
            }
            pushOp(ops, c);
        }
    }
    while (!emptyOp(ops)) {
        applyOnce(nums, ops);
    }
    double ans = 0.0;
    topNum(nums, ans);
    clearNum(nums);
    clearOp(ops);
    return ans;
}

int main() {
    string line;
    cin >> line;
    if (line.empty()) return 0;
    double ans = eval(line);
    cout << fixed << setprecision(2) << ans << '\n';
    return 0;
}

逐块精析

注：代码的变量名称中的Num指运算数、Op指运算符，后续不再赘述。

链式栈定义

struct NumNode {
    double data;
    NumNode* next;
};

struct OpNode {
    char data;
    OpNode* next;
};

在此处定义了两个不同类型的链表节点，分别用于构建存储运算数（NumNode）与运算符（OpNode）的链式栈。其中：

• NumNode 的 data 类型为 double，这是为了满足题目中“处理表达式中带小数的数据”以及后续除法运算产生浮点数的需求。
• OpNode 的 data 类型为 char，用于存储 +、-、*、/ 以及左右括号。

栈的基础操作封装

void pushNum(NumNode*& s, double x) {
    NumNode* p = new NumNode;
    p->data = x;
    p->next = s;
    s = p;
}

void pushOp(OpNode*& s, char c) {
    OpNode* p = new OpNode;
    p->data = c;
    p->next = s;
    s = p;
}

// 判空操作 (Empty)
bool emptyNum(NumNode* s) {
    return s == NULL;
}

bool emptyOp(OpNode* s) {
    return s == NULL;
}

// 出栈操作 (Pop)
void popNum(NumNode*& s) {
    if (!emptyNum(s)) {
        NumNode* p = s;
        s = s->next;
        delete p;
    }
}

void popOp(OpNode*& s) {
    if (!emptyOp(s)) {
        OpNode* p = s;
        s = s->next;
        delete p;
    }
}

// 获取栈顶元素 (Top)
bool topNum(NumNode* s, double& out) {
    if (emptyNum(s)) return false;
    out = s->data;
    return true;
}

bool topOp(OpNode* s, char& out) {
    if (emptyOp(s)) return false;
    out = s->data;
    return true;
}

// 清空栈并释放内存 (Clear)
void clearNum(NumNode*& s) {
    while (!emptyNum(s)) {
        popNum(s);
    }
}

void clearOp(OpNode*& s) {
    while (!emptyOp(s)) {
        popOp(s);
    }
}

这一部分手动实现了一个完备的链式栈结构。

• 入栈 (push())：采用头插法，将新节点插入到链表的头部，并更新头指针 s。注意参数使用了指针的引用 *&，确保对头指针的修改能反映到原变量上。
• 出栈 (pop())：在判空后，移动头指针到下一个节点，并使用 delete() 释放原栈顶节点的内存，防止内存泄漏。
• 取栈顶 (top())：通过引用参数 out 返回栈顶值，并通过布尔返回值表示是否成功获取（即栈是否为空），增强了代码的鲁棒性。

核心计算与优先级处理

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

prec() 函数用于定义运算符的优先级。乘除的优先级（2）高于加减的优先级（1），其他字符（如括号）返回 0。这是后续决定何时弹栈进行计算的关键依据。

void applyOnce(NumNode*& nums, OpNode*& ops) {
    double b, a;
    char op;
    if (!topNum(nums, b)) return; popNum(nums); // 弹出右操作数
    if (!topNum(nums, a)) return; popNum(nums); // 弹出左操作数
    if (!topOp(ops, op)) return; popOp(ops);    // 弹出运算符

    if (op == '+') pushNum(nums, a + b);
    else if (op == '-') pushNum(nums, a - b);
    else if (op == '*') pushNum(nums, a * b);
    else if (op == '/') pushNum(nums, a / b);
}

applyOnce() 封装了单次计算的过程。因为栈是 后进先出(LIFO) 的，所以先弹出的 b 是右操作数，后弹出的 a 是左操作数。这对于减法（a - b）和除法（a / b）至关重要。计算完成后，将结果重新压入运算数栈。

表达式解析主逻辑

double eval(const string& expr) {
    //栈初始化略
    for (int i = 0; i < static_cast<int>(expr.length()); ++i) {
        char c = expr[i];
        if (c == ' ') continue;
        if (c == '#') break; // 遇到结束符终止

        // ...
    }
}

遍历字符串，跳过空格（用例未包含空格，加入可使程序功能更全面），并在遇到题目要求的结束符 # 时提前结束解析。

注：此处，expr.length()的返回值类型为size_t，而for循环中的变量i的类型为int，二者类型不同。虽然编译器在绝大部分情况下可正常编译，但是在部分编译器中可能会出现警告，故此处使用static_cast<int>()将其强制转换为int类型，下同。

if (isdigit(c) || c == '.') {
    int j = i;
    while (j < static_cast<int>(expr.length()) && (isdigit(expr[j]) || expr[j] == '.')) {
        j++;
    }
    pushNum(nums, stod(expr.substr(i, j - i)));
    i = j - 1;
}

此为解决题目中“处理表达式中带小数的数据”的核心。如果当前字符是数字或小数点，利用 while 循环向后扫描，直到截取出完整的数字字符串（例如 2.53），然后使用 C++ 标准库的 stod() (string to double) 函数将其转换为双精度浮点数压栈。同时更新索引 i 以防止重复计算。

else if (c == '(') {
    pushOp(ops, c);
} else if (c == ')') {
    char topc;
    while (topOp(ops, topc) && topc != '(') {
        applyOnce(nums, ops);
    }
    if (topOp(ops, topc) && topc == '(') popOp(ops);
}

括号处理：左括号无条件入栈；遇到右括号时，不断调用 applyOnce() 计算括号内的表达式，直到遇到左括号为止，最后将左括号弹出丢弃。

else {
    char topc; 
    while (topOp(ops, topc) && topc != '(' && prec(topc) >= prec(c)) {
        applyOnce(nums, ops);
    }
    pushOp(ops, c);
}

遇到 +、-、*、/ 时，需要与栈顶运算符比较优先级。如果栈顶运算符优先级 大于或等于 当前运算符（例如当前是 +，栈顶是 *），则必须先计算之前的运算，即调用 applyOnce()。直到栈顶优先级低于当前运算符，再将当前运算符入栈。

while (!emptyOp(ops)) {
    applyOnce(nums, ops);
}
// ... 提取结果并清空栈 ...
return ans;

循环结束后，如果运算符栈中还有剩余运算符，则依次弹出并计算，最终留在 nums 栈中的唯一元素就是整个表达式的计算结果。

主函数与格式化输出

int main() {
    string line;
    cin >> line; // 接收不含空格的连续字符串，或者可改用 getline 接收含空格的式子
    if (line.empty()) return 0;
    
    double ans = eval(line);
    
    cout << fixed << setprecision(2) << ans << '\n';
    return 0;
}

主函数负责读入表达式并调用 eval() 函数。
为了满足题目中“输出数据请保留2位小数”的要求，使用了 <iomanip> 库中的 fixed 和 setprecision(2) 控制输出流的格式，确保无论计算结果的小数位数是多少，都会被格式化为两位小数输出（例如 9 会输出为 9.00，4.321 会输出为 4.32）。