如何在C++中按自定义规则排序特殊运算符列表

Great question—this is a common need when building calculators or expression evaluators, since ASCII values don’t align with mathematical operator precedence at all (for example, + has a lower ASCII value than -, but they share the same priority in standard math). Here’s a clean, flexible approach to implement your OperatorSorter function:

Core Idea: Map Operators to Priority Values #

The solution is to explicitly define a priority ranking for each operator, then use that ranking to drive the sort. We’ll use a lookup structure to assign numerical values to each operator—higher numbers mean higher precedence.

Step 1: Define the Priority Mapping #

First, create a mapping that assigns each operator to its precedence level. For your example, we’ll use:

• ^ (exponentiation): Highest priority (4)
• * and /: Next level (3)
• - and +: Lowest priority (2)

You can choose between two lookup options based on readability vs. performance:

Option 1: Using unordered_map (Readable & Maintainable)

#include <unordered_map>
#include <vector>
#include <algorithm>

void OperatorSorter(std::vector<char>& operators) {
    // Define precedence: higher value = higher priority
    std::unordered_map<char, int> opPriority = {
        {'^', 4},
        {'*', 3},
        {'/', 3},
        {'-', 2},
        {'+', 2}
    };

    // Custom sort comparator: sort operators in descending order of priority
    std::sort(operators.begin(), operators.end(), [&opPriority](char a, char b) {
        return opPriority[a] > opPriority[b];
    });
}

Option 2: Using a Fixed Array (Faster Access)

Since characters are just ASCII values, we can use a fixed-size array for O(1) lookups—ideal if you’re working with a small set of operators:

#include <vector>
#include <algorithm>

void OperatorSorter(std::vector<char>& operators) {
    // Initialize priority array (all values start at 0)
    int opPriority[256] = {0};
    opPriority['^'] = 4;
    opPriority['*'] = opPriority['/'] = 3;
    opPriority['-'] = opPriority['+'] = 2;

    std::sort(operators.begin(), operators.end(), [&opPriority](char a, char b) {
        return opPriority[a] > opPriority[b];
    });
}

Step 2: Test the Function #

Here’s a full example to verify the sorting works as expected:

#include <iostream>

int main() {
    std::vector<char> ops = {'-', '*', '/', '+', '^'};
    
    std::cout << "Original list: ";
    for (char op : ops) std::cout << op << " ";
    std::cout << "\n";

    OperatorSorter(ops);

    std::cout << "Sorted list: ";
    for (char op : ops) std::cout << op << " ";
    std::cout << "\n";
    // Output: Sorted list: ^ * / - +
    return 0;
}

Key Notes #

• Stable Sort (Optional): If you need to preserve the original order of operators with the same priority (e.g., keep * before / as they appeared in the input), replace std::sort with std::stable_sort.
• Extensibility: Adding new operators (like % for modulus) is trivial—just add them to the priority mapping with the appropriate value.
• Safety: Ensure all operators in your input list are defined in the priority mapping. If you might encounter unknown operators, add a fallback (e.g., assign priority 0 to unrecognized characters).

内容的提问来源于stack exchange，提问作者brknarsy