C++实现中缀转后缀（含赋值运算符）的逻辑疑问

Hey there! Let's work through this assignment operator problem together. It's totally understandable that this feels trickier than the arithmetic operators you've already implemented—= has two key unique traits you need to account for: right associativity and rock-bottom priority. Let's break this down step by step.

Core Traits of the Assignment Operator #

First, let's solidify the rules that govern = in expressions:

• Priority: It’s the lowest-priority operator out there—lower than +, -, *, and /. This ensures that all arithmetic operations (and any parenthesized expressions) resolve before the assignment happens.
• Right Associativity: Unlike arithmetic operators (which are left-associative, e.g., A+B+C is (A+B)+C), assignment is right-associative. That means A=B=4 is interpreted as A=(B=4)—we evaluate the rightmost assignment first, then pass that result to the left assignment.

Modifying Your Code to Support = #

Let's update your existing code to handle these rules.

1. Update the Precedence Function #

First, add = to your precedence lookup with the lowest possible value (I’ll use 0 here, since you likely have +/- at 1 and *// at 2):

int precedence(char op) {
    if (op == '*' || op == '/')
        return 2;
    if (op == '+' || op == '-')
        return 1;
    // Assign lowest priority to assignment operator
    if (op == '=')
        return 0;
    return -1; // For parentheses or other non-operator characters
}

2. Adjust the Stack Handling Logic #

Your current stack logic probably pops operators when the stack top has higher or equal precedence (for left-associative ops). For right-associative =, we only pop when the stack top has higher precedence (not equal). Here's how to adjust that loop:

// Inside your conversion loop, when processing an operator 'op'
while (!s.empty()) {
    int top_prec = precedence(s.top());
    int curr_prec = precedence(op);
    
    // Left-associative ops: pop if top precedence >= current
    // Right-associative '=': pop only if top precedence > current
    if ((op != '=' && top_prec >= curr_prec) || (op == '=' && top_prec > curr_prec)) {
        postfix += s.top();
        s.pop();
    } else {
        break;
    }
}
s.push(op);

3. Test with Your Example Cases #

Let’s verify this works with your tricky inputs:

• Case 1: A=B=4
  The conversion will produce the postfix string AB4==. When evaluated, this first computes B=4, then uses that result to compute A=(result)—perfect for right associativity.
• Case 2: A=(B=2)*2
  The postfix output will be AB2=2*=. Here, we first resolve B=2 inside the parentheses, multiply by 2, then assign the final result to A—which aligns with the operator priority rules.

Full Modified Code Snippet #

Here’s how your code might look with these changes integrated (I’ll fill in the missing parts of your original code for context):

#include <iostream>
#include <stack>
#include <string>
using namespace std;

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

bool isOperand(char c) {
    return (c >= 'A' && c <= 'Z') || (c >= 'a' && c <= 'z') || (c >= '0' && c <= '9');
}

string infixToPostfix(string infix) {
    stack<char> s;
    string postfix = "";
    
    for (char c : infix) {
        // If character is operand, add to postfix
        if (isOperand(c)) {
            postfix += c;
        }
        // If opening parenthesis, push to stack
        else if (c == '(') {
            s.push(c);
        }
        // If closing parenthesis, pop until opening parenthesis
        else if (c == ')') {
            while (!s.empty() && s.top() != '(') {
                postfix += s.top();
                s.pop();
            }
            s.pop(); // Remove the '(' from stack
        }
        // Handle operators (including =)
        else {
            while (!s.empty()) {
                int top_prec = precedence(s.top());
                int curr_prec = precedence(c);
                
                if ((c != '=' && top_prec >= curr_prec) || (c == '=' && top_prec > curr_prec)) {
                    postfix += s.top();
                    s.pop();
                } else {
                    break;
                }
            }
            s.push(c);
        }
    }
    
    // Pop remaining operators from stack
    while (!s.empty()) {
        postfix += s.top();
        s.pop();
    }
    
    return postfix;
}

int main() {
    string expr1 = "A=B=4";
    cout << "Infix: " << expr1 << "\nPostfix: " << infixToPostfix(expr1) << endl;
    
    string expr2 = "A=(B=2)*2";
    cout << "Infix: " << expr2 << "\nPostfix: " << infixToPostfix(expr2) << endl;
    
    return 0;
}

Key Takeaways #

• Always remember that assignment is right-associative—this changes how you compare precedence when popping from the stack.
• Assign = the lowest possible precedence to ensure all other operations resolve first.

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