大神的世界

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

#define MAX_SIZE 100

void infixToPrefix(char infix[]);
void parse(char infix[], int *pos, char buffer[]);

int isp(char symbol);
int icp(char symbol);

int main()
{
    char expression[] = "4 / 2 * (3+2-1) + (5-2)";
    infixToPrefix(expression);
    return 0;
}

void infixToPrefix(char infix[])
{
    // reverse the expression
    char Rinfix[MAX_SIZE];
    int len = strlen(infix);
    for(int i = len-1, j = 0; i>=0; i--){
        if(infix[i] == ')')
            Rinfix[j++] = '(';
        else if(infix[i] == '(')
            Rinfix[j++] = ')';
        else
            Rinfix[j++] = infix[i];
    }

    char result[MAX_SIZE][MAX_SIZE]; // the result needs to reverse again
    int top_result = -1;

    char token[20];
    char stack[MAX_SIZE];
    int top = -1;

    int i = 0;
    while(Rinfix[i] != '\0'){
        parse(Rinfix, &i, token);

        if(isdigit(token[0])){
            top_result++;
            int len = strlen(token);
            for(int j = 0; len; j++)
                result[top_result][j] = token[--len]; // operand is left and right reversed
        }
        else{
            if(token[0] == ')'){
                while(stack[top] != '(')
                    result[++top_result][0] = stack[top--];
                top--;
            }
            else{
                while(top >= 0 && isp(stack[top]) > icp(token[0])) // Be careful, it's > not >=
                    result[++top_result][0] = stack[top--];
                stack[++top] = token[0];
            }
        }
    }

    while(top >= 0)
        result[++top_result][0] = stack[top--];

    while(top_result >= 0)
        printf("%s", result[top_result--]);
    printf("\n");
}

void parse(char infix[], int *pos, char buffer[])
{
    int i = 0;
    while(infix[*pos] == ' ')
        (*pos)++;

    if(isdigit(infix[*pos])){
        while(isdigit(infix[*pos]))
            buffer[i++] = infix[(*pos)++];
        buffer[i] = '\0';
    }
    else
        buffer[0] = infix[(*pos)++];
}

int isp(char symbol)
{
    switch(symbol){
        case '(':
            return 1;
        case '+':
        case '-':
            return 2;
        case '*':
        case '/':
            return 3;

        default:
            printf("error occured! Unexpected symbol.\n");
            exit(1);
    }
}

int icp(char symbol)
{
    switch(symbol){
        case '(':
            return 10;
        case '+':
        case '-':
            return 2;
        case '*':
        case '/':
            return 3;

        default:
            printf("error occured! Unexpected symbol.\n");
            exit(1);
    }
}