Data_Structure/資料結構光碟檔/CH03/infixTopostfix.c.txt

/* file name: infixTopostfix.c                */
/* <20>N<EFBFBD>ƾǦ<C6BE><C7A6>l<EFBFBD>Ѥ<EFBFBD><D1A4>Ǫ<EFBFBD><C7AA>ܪk<DCAA>ର<EFBFBD><E0ACB0><EFBFBD>Ǫ<EFBFBD><C7AA>ܪk */

#include <stdio.h>
#include <stdlib.h>
#define MAX 20

void infix_to_postfix(char [], int);  /* <20>Ѥ<EFBFBD><D1A4><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>Ǩ<EFBFBD><C7A8><EFBFBD> */
int compare(char, char);  /* <20><><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ӹB<D3B9><42><EFBFBD>l<EFBFBD><6C><EFBFBD><EFBFBD> */

/* <20>b<EFBFBD><62><EFBFBD>Ǫ<EFBFBD><C7AA>ܪk<DCAA><6B><EFBFBD>C<EFBFBD>μȦs<C8A6><73><EFBFBD>|<7C><><EFBFBD>A<EFBFBD>B<EFBFBD><42><EFBFBD>l<EFBFBD><6C><EFBFBD>u<EFBFBD><75><EFBFBD><EFBFBD><EFBFBD>Ǫ<EFBFBD><C7AA>A<EFBFBD><41><EFBFBD>u<EFBFBD><75><EFBFBD>Ȭ<EFBFBD>INDEX/2 */
char infix_priority[9] = {'#', ')', '+', '-', '*', '/', '^', '('};
char stack_priority[8] = {'#', '(', '+', '-', '*', '/', '^'};

int main()
{
    int index = -1;
    char infix_q[MAX];  /* <20>x<EFBFBD>s<EFBFBD>ϥΪ̿<CEAA><CCBF>J<EFBFBD><4A><EFBFBD>Ǧ<EFBFBD><C7A6><EFBFBD><EFBFBD><EFBFBD><EFBFBD>C */
    printf("*********************************\n");
    printf("      -- Usable operator --\n");
    printf(" ^: Exponentiation\n");
    printf(" *: Multiply      /: Divide\n");
    printf(" +: Add           -: Subtraction\n");
    printf(" (: Left Brace    ): Right Brace\n");
    printf("*********************************\n");
    
    printf("<22>п<EFBFBD><D0BF>J<EFBFBD><4A><EFBFBD>Ǫ<EFBFBD><C7AA>ܦ<EFBFBD>: ");
    while (infix_q[index] != '\n')
        infix_q[++index] = getchar();
    infix_q[index] = '#';  /* <20><><EFBFBD><EFBFBD><EFBFBD>ɥ[<5B>J # <20><><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>Ÿ<EFBFBD> */
    
    printf("<22><><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>Ǫ<EFBFBD><C7AA>ܦ<EFBFBD><DCA6>p<EFBFBD>U: ");
    infix_to_postfix(infix_q, index);
    printf("\n");

    return 0;
}

void infix_to_postfix(char infix_q[], int index)
{
    int top = 0, ctr, tag = 1 ;
    char stack_t[MAX];  /* <20>ΥH<CEA5>x<EFBFBD>s<EFBFBD>٤<EFBFBD><D9A4><EFBFBD><EFBFBD><EFBFBD><EFBFBD>X<EFBFBD><58><EFBFBD>B<EFBFBD><42><EFBFBD>l */
    stack_t[top] = '#'; /* <20><><EFBFBD><EFBFBD><EFBFBD>|<7C>̩<EFBFBD><CCA9>U<EFBFBD>[<5B>J#<23><><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>Ÿ<EFBFBD> */
    for (ctr = 0; ctr <= index; ctr++) {
        switch (infix_q[ctr]) {
            /* <20><><EFBFBD>J<EFBFBD><4A> )<29>A<EFBFBD>h<EFBFBD><68><EFBFBD>X<EFBFBD><58><EFBFBD>|<7C><><EFBFBD>B<EFBFBD><42><EFBFBD>l<EFBFBD>A<EFBFBD><41><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>|<7C><><EFBFBD><EFBFBD> ( */
            case ')':
                while (stack_t[top] != '(')
                    printf("%c", stack_t[top--]);
                top--;
                break;
            /* <20><><EFBFBD>J<EFBFBD><4A> #<23>A<EFBFBD>h<EFBFBD>N<EFBFBD><4E><EFBFBD>|<7C><><EFBFBD>٥<EFBFBD><D9A5><EFBFBD><EFBFBD>X<EFBFBD><58><EFBFBD>B<EFBFBD><42><EFBFBD>l<EFBFBD><6C><EFBFBD>X */
            case '#':
                while (stack_t[top] != '#')
                    printf("%c", stack_t[top--]);
                break;
            /* <20><><EFBFBD>J<EFBFBD><4A><EFBFBD>B<EFBFBD><42><EFBFBD>l<EFBFBD>A<EFBFBD>Y<EFBFBD>p<EFBFBD><70>TOP<4F>b<EFBFBD><62><EFBFBD>|<7C><><EFBFBD>ҫ<EFBFBD><D2AB>B<EFBFBD><42><EFBFBD>l<EFBFBD>A<EFBFBD>h<EFBFBD>N<EFBFBD><4E><EFBFBD>|
                <20><><EFBFBD>B<EFBFBD><42><EFBFBD>l<EFBFBD><6C><EFBFBD>X<EFBFBD>A<EFBFBD><41><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>|<7C><><EFBFBD><EFBFBD><EFBFBD>B<EFBFBD><42><EFBFBD>l<EFBFBD>p<EFBFBD><70><EFBFBD><EFBFBD><EFBFBD>J<EFBFBD><4A><EFBFBD>B<EFBFBD><42><EFBFBD>l<EFBFBD>A
                <20>Y<EFBFBD>j<EFBFBD>󵥩<EFBFBD>TOP<4F>b<EFBFBD><62><EFBFBD>|<7C><><EFBFBD>ҫ<EFBFBD><D2AB>B<EFBFBD><42><EFBFBD>l<EFBFBD>A<EFBFBD>h
                <20>N<EFBFBD><4E><EFBFBD>J<EFBFBD><4A><EFBFBD>B<EFBFBD><42><EFBFBD>l<EFBFBD>m<EFBFBD>J<EFBFBD><4A><EFBFBD>| */

            case '(':
            case '^':
            case '*':
            case '/':
                while (compare(stack_t[top], infix_q[ctr]))
                    printf("%c", stack_t[top--]);
                stack_t[++top] = infix_q[ctr];
                tag = 1;
                break;
            case '+':
            case '-':
                if (tag == 1) { /* <20>P<EFBFBD>_ (<28>A^<5E>A*<2A>A/ <20>᪺ - <20><><EFBFBD>O<EFBFBD>_<EFBFBD><5F><EFBFBD>ܭt<DCAD><74> */
                    stack_t[++top] = infix_q[ctr];
                    tag = 2;  /* <20>N tag <20>]<5D><> 2 */
                }
                else {
                    while (compare(stack_t[top], infix_q[ctr]))
                        printf("%c", stack_t[top--]);
                    stack_t[++top] = infix_q[ctr];
                    tag = 1;
                }
                break;
            /* <20><><EFBFBD>J<EFBFBD><4A><EFBFBD>B<EFBFBD>⤸<EFBFBD>A<EFBFBD>h<EFBFBD><68><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>X */
            default:
                printf("%c", infix_q[ctr]);
                if (tag == 2) /* <20>N<EFBFBD>s<EFBFBD><73><EFBFBD>b<EFBFBD><62><EFBFBD>|<7C><><EFBFBD>t<EFBFBD><74><EFBFBD><EFBFBD><EFBFBD>X */
                    printf("%c", stack_t[top--]);
                tag = 0;
                break;
        }
    }
}

/* <20><><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>B<EFBFBD><42><EFBFBD>l<EFBFBD>u<EFBFBD><75><EFBFBD>v<EFBFBD>A<EFBFBD>Y<EFBFBD><59><EFBFBD>J<EFBFBD>B<EFBFBD><42><EFBFBD>l<EFBFBD>p<EFBFBD><70><EFBFBD><EFBFBD><EFBFBD>|<7C><><EFBFBD>B<EFBFBD><42><EFBFBD>l<EFBFBD>A<EFBFBD>h<EFBFBD>Ǧ^<5E>Ȭ<EFBFBD> 1<>A<EFBFBD>_<EFBFBD>h<EFBFBD><68> 0 */
int compare(char stack_o, char infix_o)
{
    int index_s = 0, index_i = 0;
    while (stack_priority[index_s] != stack_o)
        index_s++;
    while (infix_priority[index_i] != infix_o)
        index_i++;
    return index_s/2 >= index_i/2 ? 1 : 0;
}