report

algorithm1.c

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

#define BUFLEN 80
#define STKLMT 100

char STACK[STKLMT];
int StkCtr;

void push (char *c) {
    if (StkCtr >= STKLMT) {
        printf("Error-- STACK Overflow\n");
        exit(1);
    }
    STACK[StkCtr] = *c;
    StkCtr++;
}

void pop(char *c) {
    if(StkCtr <= 0) {
        printf("Error-- STACK Empty\n");
        exit(1);
    }
    StkCtr--;
    *c = STACK[StkCtr];
}

int charac(char c) {
    char variable[26] = {"abcdefghijklmnopqrstuvwxyz"},
         oper[4] = {"+-*/"},
         oper2[2] = {"()"};
    int i;
    for(i=0;i<26;i++) if(c==variable[i]) return 1;
    for(i=0;i<4;i++)  if(c==oper[i]) return 2;
    for(i=0;i<2;i++)  if(c==oper2[i]) return 3;
    return 0;
}

int check_operate(char c) {
    if(c == '+' || c == '-') return 1;
    else if(c == '*' || c == '/') return 2;
}

void polish(char str[], char r_polish[]) {
    int str_size = strlen(str);
    int r_polish_i = 0;
    int i;
    char c;
    for(i = 0;i < str_size;i++) {
        int r = charac(str[i]);
        if(r == 1) {
            //変数の場合
            r_polish[r_polish_i] = str[i];
            r_polish_i++;
        }else if(r == 2) {
            //演算子の場合
            if(StkCtr <= 0) {
                push(&str[i]);
            }else {
                int c_num = check_operate(str[i]);
                int c_stack_num = check_operate(STACK[0]);
                if(c_num >= c_stack_num) {
                    //そのまま入れる
                    push(&str[i]);
                }else {
                    while(c_num < c_stack_num) {
                        pop(&c);
                        r_polish[r_polish_i] = c;
                        r_polish_i++;
                        if(StkCtr >= 1) c_stack_num = check_operate(STACK[0]);
                        else c_stack_num = 0;
                    }
                    push(&str[i]);
                }
            }
        }else if(r == 3) {
            //()の場合
            if(str[i] == '(') {
                push(&str[i]);
            }else {
                pop(&c);
                while(c != '(') {
                    r_polish[r_polish_i] = c;
                    r_polish_i++;
                    pop(&c);
                }
            }
       }

    }

    while(StkCtr >= 1) {
        pop(&c);
        r_polish[r_polish_i] = c;
        r_polish_i++;
    }
    r_polish[r_polish_i]='\0';
    r_polish_i++;
}

void code(char r_polish[]) {
    int r_polish_size = strlen(r_polish);
    char st[36]="0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"; 
    int st_i = 0;
    int i;
    char c;
    for(i = 0;i < r_polish_size;i++) {
        int r = charac(r_polish[i]);
        if(r == 1) {
            push(&r_polish[i]);
        }else {
            pop(&c);
            char c2 = c;
            pop(&c);
            char c1 = c;

            printf("T%c <- ", st[st_i]);
            if(charac(c1) == 1) printf("%c %c ", c1, r_polish[i]);
            else                printf("T%c %c ", c1, r_polish[i]);

            if(charac(c2) == 1) printf("%c\n", c2);
            else                printf("T%c\n", c2);

            push(&st[st_i]);
            st_i++;
        }
    }

}

int main() {
    char str[BUFLEN];
    char r_polish[BUFLEN];

    fgets(str, BUFLEN,stdin);
    polish(str, r_polish);

    printf("Reverse Polish notation ... %s\n", r_polish);
    int r_polish_size = strlen(r_polish);
    printf("length=%d\n", r_polish_size);
    
    printf("Intermediate Code\n");

    code(r_polish);
}