题解 | #计算表达式#

#include <stdio.h>
#include <stdbool.h>
// 计算字符串长度：
int Length(char a[]) {
    int n = 0;
    for (int i = 0; a[i] != '\0'; i++) {
        n++;
    }
    return n;
}
#define MAXSIZE 30
typedef struct {
    char data[MAXSIZE];
    int top;
} Stack;
typedef struct {
    float data[MAXSIZE];
    int top;
} Stack_int;
// 初始化一个字符栈：
void InitStackc(Stack* S) {
    S->top = -1;
}
// 初始化一个数字栈：
void InitStack(Stack_int* S) {
    S->top = -1;
}
// 栈判空：
bool StackEmpty(Stack S) {
    if (S.top == -1) {
        return true;
    } else
        return false;
}
// 进栈：
bool Push(Stack_int* S, float x) {
    if (S->top == MAXSIZE - 1)
        return false;
    else {
        S->data[++S->top] = x;
        return true;
    }
}
// 字符（专用）进栈：
bool Pushc(Stack* S, char x) {
    if (S->top == MAXSIZE - 1)
        return false;
    else {
        S->data[++S->top] = x;
        return true;
    }
}
// 出栈：
bool Pop(Stack_int* S, float* x) {
    if (S->top != -1) {
        *x = S->data[S->top--];
        return true;
    } else
        return false;
}
// 字符（专用）出栈：
bool Popc(Stack* S, char* x) {
    if (S->top != -1) {
        *x = S->data[S->top--];
        return true;
    } else
        return false;
}
// 读取栈顶元素：
bool GetTop(Stack_int S, float* x) {
    if (S.top == -1)
        return false;
    else {
        *x = S.data[S.top];
        return true;
    }
}
// 读取栈顶元素(字符专用)：
bool GetTopc(Stack S, char* x) {
    if (S.top == -1)
        return false;
    else {
        *x = S.data[S.top];
        return true;
    }
}
// 中缀转后缀：(以空格分割)
void InfixToSuffix(char a[]) {
    int len = Length(a);
    char b[len];
    Stack S;
    InitStackc(&S);
    int j = 0;
    char number;
    for (int i = 0; i < len; i++) {
        if (a[i] == '(')
            Pushc(&S, a[i]);
        else if (a[i] == '+' || a[i] == '-') {
            while (1) {
                if (S.top == -1 || S.data[S.top] == '(')
                    break;
                Popc(&S, &number);
                b[j++] = number;
                b[j++] = ' ';
            }
            Pushc(&S, a[i]);
        } else if (a[i] == '*' || a[i] == '/') {
            while (1) {
                if (S.top == -1 || S.data[S.top] == '(' || S.data[S.top] == '+' ||
                        S.data[S.top] == '-')
                    break;
                else if (S.data[S.top] == '*' || S.data[S.top] == '/') {
                    Popc(&S, &number);
                    b[j++] = number;
                    b[j++] = ' ';
                }
            }
            Pushc(&S, a[i]);
        } else if (a[i] == ')') {
            while (S.data[S.top] != '(') {
                Popc(&S, &number);
                b[j++] = number;
                b[j++] = ' ';
            }

            S.top--;
        } else if (a[i] == ' ')
            continue;
        else {
            if (a[i + 1] == ' ' || (a[i + 1] == '\0' && !StackEmpty(S))) {
                b[j++] = a[i];
                b[j++] = ' ';
            } else {
                b[j++] = a[i];
            }
        }
    }
    while (!StackEmpty(S)) {
        Popc(&S, &number);
        if (j < len - 1) {
            b[j++] = number;
            b[j++] = ' ';
        } else if (j == len - 1) {
            b[j++] = number;
        }
    }

    for (int i = 0; i < len; i++) {
        a[i] = b[i];
    }
}
// 中缀转后缀：（不以空格分割）
void InfixToSuffix_e(char a[]) {
    int len = Length(a);
    char b[100] = "";
    Stack S;
    InitStackc(&S);
    int j = 0;
    char number;
    for (int i = 0; i < len; i++) {
        if (a[i] >= 48 && a[i] <= 57) {
            if (a[i + 1] < 48 || a[i + 1] > 57) {
                b[j++] = a[i];
                b[j++] = ' ';
            } else {
                b[j++] = a[i];
            }
        } else if (a[i] == '(')
            Pushc(&S, a[i]);
        else if (a[i] == '+' || a[i] == '-') {
            while (1) {
                if (S.top == -1 || S.data[S.top] == '(')
                    break;
                Popc(&S, &number);
                b[j++] = number;
                b[j++] = ' ';
            }
            Pushc(&S, a[i]);
        } else if (a[i] == '*' || a[i] == '/') {
            while (1) {
                if (S.top == -1 || S.data[S.top] == '(' || S.data[S.top] == '+' ||
                        S.data[S.top] == '-')
                    break;
                else if (S.data[S.top] == '*' || S.data[S.top] == '/') {
                    Popc(&S, &number);
                    b[j++] = number;
                    b[j++] = ' ';
                }
            }
            Pushc(&S, a[i]);
        } else if (a[i] == ')') {
            while (S.data[S.top] != '(') {
                Popc(&S, &number);
                b[j++] = number;
                b[j++] = ' ';
            }
            S.top--;
        }
    }
    while (!StackEmpty(S)) {
        Popc(&S, &number);
        b[j++] = number;
        b[j++] = ' ';
    }
    int n = Length(b);
    for (int k = 0; k < n; k++) {
        a[k] = b[k];
    }
}
// 后缀计算：
int CalSuffix(char a[]) {
    Stack_int S;
    InitStack(&S);
    int len = Length(a);
    int i = 0;
    while (i < len) {
        if ((a[i] >= '0' && a[i] <= '9')) {
            int num = a[i] - '0';
            while (a[i + 1] != ' ') {
                num = num * 10 + (a[i + 1] - '0');
                i++;
            }
            Push(&S, num);
            i++;
        } else if (a[i] == ' ') {
            i++;
            continue;
        } else {
            float m, n, number;
            Pop(&S, &n);
            Pop(&S, &m);
            switch (a[i]) {
                case '+':
                    number = m + n;
                    Push(&S, number);
                    break;
                case '-':
                    number = m - n;
                    Push(&S, number);
                    break;
                case '*':
                    number = m * n;
                    Push(&S, number);
                    break;
                case '/':
                    number = m / n;
                    Push(&S, number);
                    break;
            }
            i++;
        }
    }
    return S.data[S.top];
}
int main() {
    char a[50] = "";
    gets(a);
    int x = 0;
    InfixToSuffix_e(a);
    x = CalSuffix(a);
    printf("%d\n", x);
    return 0;
}