中缀表达式转后缀及求值代码适配空格与多位数需求

Got it, let's get your code working with spaces and multi-digit numbers while ensuring the postfix output is properly formatted (with spaces between elements for readability). Here's the revised code, followed by a breakdown of the key fixes and additions:

#include <stdio.h>
#include <ctype.h>
#include <string.h>

char stack[100];
int top = -1;  // Fixed: Initialize top to -1 for empty stack
int eval_top = -1;
int eval_stack[100];

// Push char into operator stack
void push(char x) {
    stack[++top] = x;  // Adjusted: Increment top first then assign
}

// Pop char from operator stack
char pop() {
    if (top == -1)
        return -1;
    else
        return stack[top--];
}

// Push integer into evaluation stack
void eval_push(int x) {
    eval_stack[++eval_top] = x;
}

// Pop integer from evaluation stack
int eval_pop() {
    if (eval_top == -1) {
        return -1;
    } else {
        return eval_stack[eval_top--];
    }
}

// Check operator priority
int priority(char x) {
    if (x == '(')
        return 0;
    if (x == '+' || x == '-')
        return 1;
    if (x == '*' || x == '/')
        return 2;
    return -1;  // Added default return for safety
}

// Evaluate postfix expression (handles space-separated elements)
void EvalPostfix(char postfix[]) {
    int A, B;
    int val;
    char *token = strtok(postfix, " ");  // Split postfix by spaces

    while (token != NULL) {
        if (isdigit(token[0])) {
            // Convert token string to integer
            eval_push(atoi(token));
        } else if (strlen(token) == 1 && strchr("+-*/", token[0]) != NULL) {
            A = eval_pop();
            B = eval_pop();
            switch (token[0]) {
                case '*': val = B * A; break;
                case '/': val = B / A; break;
                case '+': val = B + A; break;
                case '-': val = B - A; break;
                default: val = 0;  // Fallback for invalid ops
            }
            eval_push(val);
        }
        token = strtok(NULL, " ");
    }
    printf("\nResult: %d\n", eval_pop());
}

int main() {
    int i = 0;
    char x;
    char postfix[200];  // Increased size for space-separated elements
    char exp[100];

    printf("Infix expression: ");
    fgets(exp, sizeof(exp), stdin);  // Use fgets to read spaces
    // Remove trailing newline from fgets
    exp[strcspn(exp, "\n")] = '\0';

    printf("Postfix expression: ");
    char *e = exp;
    while (*e != '\0') {
        if (isspace(*e)) {
            // Skip spaces entirely
            e++;
            continue;
        } else if (isdigit(*e)) {
            // Handle multi-digit numbers: read all consecutive digits
            int num_start = i;
            while (isdigit(*e)) {
                postfix[i++] = *e;
                e++;
            }
            postfix[i++] = ' ';  // Add space after number for separation
            // Print the number
            for (int j = num_start; j < i-1; j++) {
                printf("%c", postfix[j]);
            }
            printf(" ");
        } else if (*e == '(') {
            push(*e);
            e++;
        } else if (*e == ')') {
            while ((x = pop()) != '(') {
                postfix[i++] = x;
                postfix[i++] = ' ';  // Add space after operator
                printf("%c ", x);
            }
            e++;
        } else if (strchr("+-*/", *e) != NULL) {
            // Handle operators based on priority
            while (top != -1 && priority(stack[top]) >= priority(*e)) {
                x = pop();
                postfix[i++] = x;
                postfix[i++] = ' ';
                printf("%c ", x);
            }
            push(*e);
            e++;
        } else {
            // Skip invalid characters
            e++;
        }
    }
    // Pop remaining operators from stack
    while (top != -1) {
        x = pop();
        postfix[i++] = x;
        postfix[i++] = ' ';
        printf("%c ", x);
    }
    // Remove trailing space from postfix
    if (i > 0) {
        postfix[i-1] = '\0';
    } else {
        postfix[0] = '\0';
    }
    // Print a newline before result
    printf("\n");
    EvalPostfix(postfix);

    return 0;
}

Key Changes Explained: #

• Space Handling:
  • Replaced scanf with fgets to read input containing spaces.
  • Added a check to skip space characters during expression traversal, so they don't affect the conversion.
• Multi-Digit Numbers:
  • When a digit is encountered, we read all consecutive digits to form a complete number, then add it as a single element in the postfix expression (followed by a space).
  • In the evaluation function, we use strtok to split the postfix string by spaces, then convert each numeric token to an integer with atoi.
• Stack Initialization Fix:
  • Corrected the operator stack's initial top value to -1 (original code had top=0, which caused incorrect empty-stack checks in pop()).
  • Adjusted the push function to increment top before assigning the value, which aligns with the -1 initial state.
• Postfix Formatting:
  • Added spaces between all elements (numbers and operators) in the postfix output for readability, matching your required output examples.
  • Removed trailing spaces from the postfix string to avoid issues during evaluation.
• Robustness Improvements:
  • Added a default return value in priority() for safety.
  • Handled invalid characters by skipping them.
  • Used strcspn to remove the trailing newline added by fgets.

Test Cases: #

1. Input: (7-3)/(2+2) → Postfix: 7 3 - 2 2 + / → Result: 1
2. Input: (7 - 3) / (2 + 2) → Postfix: 7 3 - 2 2 + / → Result: 1
3. Input: (22 - 10)/(2 + 2) → Postfix: 22 10 - 2 2 + / → Result: 3

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