用代码解析一阶谓词公式

Question

2.程序功能
读入项的表达式（不含空格）。
首先输出项的层数，再按照层数由小到大输出表达式中的项，每层的项按照在表达式中的顺序输出（如同一项在表达式中多次出现，则要多次输出），中间用英文分号分开，每层输出完毕输出回车符。

不同的项（函数、个体常元、个体变元）可能使用相同的标识符

3.样例
输入：
f(f(g(a,b),x,h(c)),a(j,c),h(a))
输出：
3
a;b;x;c;j;c;a
g(a,b);h(c);a(j,c);h(a)
f(g(a,b),x,h(c))
f(f(g(a,b),x,h(c)),a(j,c),h(a))

Answer 1

引自免费微信小程序：皆我百晓生

为了实现这个功能，我们可以创建一个简单的递归函数来遍历给定的一阶谓词公式，并计算其中的层次。这里是一个C++的解决方案，它包括一个parseFormula函数来处理解析工作，以及一个辅助函数printItem用于打印项。

#include <iostream>
#include <string>
#include <vector>
#include <unordered_set>
#include <stack>

// 用于存储项和它们的索引
struct Item {
    std::string name;
    int index;

    bool operator==(const Item& other) const {
        return name == other.name && index == other.index;
    }
};

std::vector<Item> parseFormula(const std::string& formula, int depth = 0);
void printItem(const Item& item, std::unordered_set<std::string>& printedItems);

int main() {
    std::string formula = "f(f(g(a,b),x,h(c)),a(j,c),h(a))";
    std::cout << "层数: " << parseFormula(formula).size() << "\n";

    // 打印所有项
    for (const auto& item : parseFormula(formula)) {
        if (!printedItems.count(item.name)) {
            printItem(item, printedItems);
            printedItems.insert(item.name);
        }
    }

    return 0;
}

std::vector<Item> parseFormula(const std::string& formula, int depth) {
    std::vector<Item> items;
    std::stack<char> brackets;
    std::stack<Item> itemStack;
    std::string currentItem;
    int startIndex = 0;

    for (size_t i = 0; i < formula.size(); ++i) {
        char c = formula[i];

        if (c == '(') {
            brackets.push('(');
        } else if (c == ')') {
            if (brackets.empty()) {
                throw std::runtime_error("Invalid formula");
            }
            brackets.pop();
            if (brackets.empty()) {
                items.push_back({currentItem, startIndex});
                currentItem.clear();
                startIndex = i + 1;
            }
        } else if (c == ',' && brackets.empty()) {
            items.push_back({currentItem, startIndex});
            currentItem.clear();
            startIndex = i + 1;
        } else {
            currentItem += c;
        }
    }

    if (!brackets.empty()) {
        throw std::runtime_error("Invalid formula");
    }

    // 如果还有未结束的项目，将其添加到结果中
    if (!currentItem.empty()) {
        items.push_back({currentItem, startIndex});
    }

    // 递归处理嵌套的括号
    for (auto it = items.begin(); it != items.end(); ) {
        if (it->name[0] == '(') {
            std::vector<Item> subItems = parseFormula(it->name.substr(1, it->name.size() - 2), depth + 1);
            for (const auto& subItem : subItems) {
                subItem.index = it->index;
                items.erase(it);
                it = items.insert(it, subItem);
            }
        } else {
            ++it;
        }
    }

    return items;
}

void printItem(const Item& item, std::unordered_set<std::string>& printedItems) {
    if (item.name.find('(') == std::string::npos) {
        std::cout << item.name << ";";
        printedItems.insert(item.name);
    } else {
        std::cout << item.name << " ";
        printItem(Item{"", item.index}, printedItems);
    }
}

这个程序首先定义了一个结构体Item来存储项的名称和其在原公式中的起始位置。然后我们有一个主函数，它读取输入字符串并调用parseFormula函数来分析公式。parseFormula函数使用了栈来跟踪嵌套的括号，同时收集所有的项。printItem函数负责将项按照要求格式化输出。

请注意，这个程序没有处理一些特殊情况，例如空格和特殊字符。在实际应用中，你可能需要对输入进行预处理，确保它符合预期的格式。