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

/* ---- constants ---- */
#define MAXLINES 1000
#define MAXBUF   256
#define MAXVARS  256
#define MAXSTACK 256
#define MAXDATA  1024

/* ---- program storage ---- */
typedef struct { int num; char text[MAXBUF]; } Line;
Line program[MAXLINES];
int prog_cnt = 0;

/* ---- variables (numeric only for now) ---- */
char var_names[MAXVARS][3];
double var_vals[MAXVARS];
int var_cnt = 0;

/* ---- DATA pool ---- */
double data_pool[MAXDATA];
int data_count = 0;
int data_pos   = 0;

/* ---- GOSUB stack (BAKSTK) ---- */
int call_stack[MAXSTACK];
int call_sp = 0;

/* ---- FOR/NEXT stack ---- */
typedef struct { int var_idx; double limit; double step; int line_idx; } ForEntry;
ForEntry for_stack[MAXSTACK];
int for_sp = 0;

/* ---- globals ---- */
double fac;
int cur_line_idx;    /* index into program[] */
int running;

/* ============================================================
   FIND_LINE - like SRCHLN
   ============================================================ */
int find_line(int num) {
    for (int i = 0; i < prog_cnt; i++)
        if (program[i].num == num) return i;
    return -1;
}

/* ============================================================
   PTRGET - find or create variable
   ============================================================ */
int ptrget(const char *name) {
    char n[3] = {0};
    n[0] = toupper(name[0]);
    if (isalnum(name[1])) n[1] = toupper(name[1]);
    for (int i = 0; i < var_cnt; i++)
        if (strcmp(n, var_names[i]) == 0) return i;
    strcpy(var_names[var_cnt], n);
    var_vals[var_cnt] = 0.0;
    return var_cnt++;
}

/* ============================================================
   EXPRESSION PARSER (EVAL / OPRND)
   Supports: numbers, variables, +,-,*,/,^,(),ABS,SQR,RND,INT
   ============================================================ */
double expr(char **p);

static void skip_ws(char **p) { while (**p == ' ') (*p)++; }

static double primary(char **p) {
    skip_ws(p);
    double x = 0;
    /* Unary minus */
    if (**p == '-') { (*p)++; return -primary(p); }
    /* Parenthesis */
    if (**p == '(') {
        (*p)++;
        x = expr(p);
        skip_ws(p);
        if (**p == ')') (*p)++;
        return x;
    }
    /* String check: ABS, SQR, RND, INT */
    if (strncasecmp(*p, "ABS(", 4) == 0) { *p+=4; x=fabs(expr(p)); skip_ws(p); if(**p==')')(*p)++; return x; }
    if (strncasecmp(*p, "SQR(", 4) == 0) { *p+=4; x=sqrt(expr(p)); skip_ws(p); if(**p==')')(*p)++; return x; }
    if (strncasecmp(*p, "INT(", 4) == 0) { *p+=4; x=floor(expr(p)); skip_ws(p); if(**p==')')(*p)++; return x; }
    if (strncasecmp(*p, "RND(", 4) == 0) { *p+=4; expr(p); skip_ws(p); if(**p==')')(*p)++; return (double)rand()/RAND_MAX; }
    if (strncasecmp(*p, "SIN(", 4) == 0) { *p+=4; x=sin(expr(p)); skip_ws(p); if(**p==')')(*p)++; return x; }
    if (strncasecmp(*p, "COS(", 4) == 0) { *p+=4; x=cos(expr(p)); skip_ws(p); if(**p==')')(*p)++; return x; }
    if (strncasecmp(*p, "LOG(", 4) == 0) { *p+=4; x=log(expr(p)); skip_ws(p); if(**p==')')(*p)++; return x; }
    if (strncasecmp(*p, "EXP(", 4) == 0) { *p+=4; x=exp(expr(p)); skip_ws(p); if(**p==')')(*p)++; return x; }
    /* Number literal */
    if (isdigit(**p) || **p == '.') {
        char *end; x = strtod(*p, &end); *p = end; return x;
    }
    /* Variable */
    if (isalpha(**p)) {
        char name[3] = {0};
        name[0] = toupper(*(*p)++);
        if (isalnum(**p)) name[1] = toupper(*(*p)++);
        return var_vals[ptrget(name)];
    }
    return 0;
}

static double power(char **p) {
    double x = primary(p);
    skip_ws(p);
    if (**p == '^') { (*p)++; x = pow(x, primary(p)); }
    return x;
}

static double term(char **p) {
    double x = power(p);
    skip_ws(p);
    while (**p == '*' || **p == '/') {
        char op = *(*p)++;
        double y = power(p);
        x = (op == '*') ? x*y : x/y;
        skip_ws(p);
    }
    return x;
}

double expr(char **p) {
    double x = term(p);
    skip_ws(p);
    while (**p == '+' || **p == '-') {
        char op = *(*p)++;
        double y = term(p);
        x = (op == '+') ? x+y : x-y;
        skip_ws(p);
    }
    return fac = x;
}

/* Relational: returns 1/0 */
double rel_expr(char **p) {
    double x = expr(p);
    skip_ws(p);
    if (strncmp(*p,"<>",2)==0) { *p+=2; return x != expr(p); }
    if (strncmp(*p,"<=",2)==0) { *p+=2; return x <= expr(p); }
    if (strncmp(*p,">=",2)==0) { *p+=2; return x >= expr(p); }
    if (**p=='<') { (*p)++; return x < expr(p); }
    if (**p=='>') { (*p)++; return x > expr(p); }
    if (**p=='=') { (*p)++; return x == expr(p); }
    return x;
}

/* ============================================================
   COLLECT DATA (FDTLP)
   ============================================================ */
void collect_data() {
    data_count = 0; data_pos = 0;
    for (int i = 0; i < prog_cnt; i++) {
        char *p = program[i].text;
        while (*p && strncasecmp(p,"DATA",4)!=0) p++;
        if (!*p) continue;
        p += 4;
        while (*p) {
            skip_ws(&p);
            if (*p == ',') p++;
            skip_ws(&p);
            if (!*p) break;
            char *end; double v = strtod(p,&end);
            if (end != p) { data_pool[data_count++] = v; p = end; }
            else break;
        }
    }
}

/* ============================================================
   INSERT LINE (PROMPT / TOKENIZE)
   ============================================================ */
void insert_line(int num, char *text) {
    /* Replace existing */
    for (int i = 0; i < prog_cnt; i++) {
        if (program[i].num == num) {
            if (!text || !*text) {
                /* Delete */
                for (int j = i; j < prog_cnt-1; j++) program[j]=program[j+1];
                prog_cnt--; return;
            }
            strncpy(program[i].text, text, MAXBUF-1);
            return;
        }
    }
    if (!text || !*text) return;
    /* Insert sorted */
    program[prog_cnt].num = num;
    strncpy(program[prog_cnt].text, text, MAXBUF-1);
    prog_cnt++;
    /* Bubble sort by line number */
    for (int i = prog_cnt-1; i > 0 && program[i].num < program[i-1].num; i--) {
        Line tmp = program[i]; program[i] = program[i-1]; program[i-1] = tmp;
    }
}

/* ============================================================
   EXECUTE ONE LINE (NEWSTT / EXEC / FNCTAB)
   ============================================================ */
void execute_line(char *stmt);
void run_from(int idx);

void execute_stmt(char *p) {
    skip_ws(&p);
    /* REM / ' */
    if (strncasecmp(p,"REM",3)==0 || *p=='\'') return;
    /* PRINT */
    if (strncasecmp(p,"PRINT",5)==0) {
        p += 5;
        while (*p) {
            skip_ws(&p);
            if (!*p) break;
            if (*p == '"') {
                p++;
                while (*p && *p!='"') putchar(*p++);
                if (*p=='"') p++;
            } else if (*p==';') { p++; continue; }
            else if (*p==',') { printf("\t"); p++; continue; }
            else { printf("%g", rel_expr(&p)); }
            skip_ws(&p);
        }
        printf("\n");
        return;
    }
    /* INPUT */
    if (strncasecmp(p,"INPUT",5)==0) {
        p += 5; skip_ws(&p);
        if (*p=='"') { p++; while(*p && *p!='"') putchar(*p++); if(*p=='"')p++; if(*p==',')p++; printf("? "); }
        else printf("? ");
        char name[3]={0}; name[0]=toupper(*p++); if(isalnum(*p)) name[1]=toupper(*p++);
        double v; scanf("%lf",&v); getchar();
        var_vals[ptrget(name)] = v;
        return;
    }
    /* LET or assignment */
    if (strncasecmp(p,"LET",3)==0) p+=3;
    /* Detect assignment: name = */
    if (isalpha(*p)) {
        char name[3]={0}; char *save=p;
        name[0]=toupper(*p++); if(isalnum(*p)) name[1]=toupper(*p++);
        skip_ws(&p);
        if (*p=='=') {
            p++; var_vals[ptrget(name)] = expr(&p); return;
        }
        p = save;
    }
    /* IF */
    if (strncasecmp(p,"IF",2)==0) {
        p+=2; skip_ws(&p);
        double cond = rel_expr(&p);
        skip_ws(&p);
        if (strncasecmp(p,"THEN",4)==0) p+=4;
        skip_ws(&p);
        if (cond) execute_stmt(p);
        return;
    }
    /* GOTO */
    if (strncasecmp(p,"GOTO",4)==0) {
        p+=4; int tgt=(int)expr(&p);
        int idx=find_line(tgt);
        if (idx<0) { printf("?Undefined line %d\n",tgt); running=0; return; }
        cur_line_idx = idx; running = 2; return;
    }
    /* GOSUB */
    if (strncasecmp(p,"GOSUB",5)==0) {
        p+=5; int tgt=(int)expr(&p);
        int idx=find_line(tgt);
        if (idx<0) { printf("?Undefined line %d\n",tgt); running=0; return; }
        call_stack[call_sp++] = cur_line_idx+1;
        cur_line_idx = idx; running = 2; return;
    }
    /* RETURN */
    if (strncasecmp(p,"RETURN",6)==0) {
        if (call_sp<=0) { printf("?RETURN without GOSUB\n"); running=0; return; }
        cur_line_idx = call_stack[--call_sp]; running = 2; return;
    }
    /* FOR */
    if (strncasecmp(p,"FOR",3)==0) {
        p+=3; skip_ws(&p);
        char name[3]={0}; name[0]=toupper(*p++); if(isalnum(*p)) name[1]=toupper(*p++);
        skip_ws(&p); if(*p=='=') p++;
        double start=expr(&p);
        skip_ws(&p); if(strncasecmp(p,"TO",2)==0) p+=2;
        double limit=expr(&p);
        double step=1.0;
        skip_ws(&p); if(strncasecmp(p,"STEP",4)==0) { p+=4; step=expr(&p); }
        int vi=ptrget(name); var_vals[vi]=start;
        for_stack[for_sp].var_idx=vi;
        for_stack[for_sp].limit=limit;
        for_stack[for_sp].step=step;
        for_stack[for_sp].line_idx=cur_line_idx;
        for_sp++;
        return;
    }
    /* NEXT */
    if (strncasecmp(p,"NEXT",4)==0) {
        if (for_sp<=0) { printf("?NEXT without FOR\n"); running=0; return; }
        ForEntry *fe = &for_stack[for_sp-1];
        var_vals[fe->var_idx] += fe->step;
        if ((fe->step>0 && var_vals[fe->var_idx] <= fe->limit) ||
            (fe->step<0 && var_vals[fe->var_idx] >= fe->limit)) {
            cur_line_idx = fe->line_idx; running=2;
        } else { for_sp--; }
        return;
    }
    /* READ */
    if (strncasecmp(p,"READ",4)==0) {
        p+=4; skip_ws(&p);
        while(*p) {
            skip_ws(&p);
            if(*p==',') p++;
            skip_ws(&p);
            if(!*p) break;
            char name[3]={0}; name[0]=toupper(*p++); if(isalnum(*p)) name[1]=toupper(*p++);
            if (data_pos>=data_count) { printf("?Out of DATA\n"); running=0; return; }
            var_vals[ptrget(name)] = data_pool[data_pos++];
        }
        return;
    }
    /* RESTORE */
    if (strncasecmp(p,"RESTORE",7)==0) { data_pos=0; return; }
    /* DATA */
    if (strncasecmp(p,"DATA",4)==0) return;  /* handled at collect time */
    /* END / STOP */
    if (strncasecmp(p,"END",3)==0 || strncasecmp(p,"STOP",4)==0) { running=0; return; }
    /* LIST */
    if (strncasecmp(p,"LIST",4)==0) {
        for(int i=0;i<prog_cnt;i++) printf("%d %s\n",program[i].num,program[i].text);
        return;
    }
    /* RUN */
    if (strncasecmp(p,"RUN",3)==0) {
        collect_data(); data_pos=0; call_sp=0; for_sp=0; var_cnt=0;
        run_from(0); return;
    }
    /* NEW */
    if (strncasecmp(p,"NEW",3)==0) { prog_cnt=0; var_cnt=0; call_sp=0; for_sp=0; data_count=0; printf("Ok\n"); return; }
    /* CLEAR */
    if (strncasecmp(p,"CLEAR",5)==0) { var_cnt=0; call_sp=0; for_sp=0; data_pos=0; return; }
    /* DIM stub */
    if (strncasecmp(p,"DIM",3)==0) return;

    printf("?Syntax error\n");
}

/* Execute multiple statements on one line (: separated) */
void execute_line(char *text) {
    char buf[MAXBUF]; strncpy(buf,text,MAXBUF-1);
    char *tok = strtok(buf,":");
    while (tok && running) {
        execute_stmt(tok);
        tok = strtok(NULL,":");
    }
}

/* RUN loop from line index */
void run_from(int idx) {
    running = 1;
    cur_line_idx = idx;
    while (running && cur_line_idx < prog_cnt) {
        int save = cur_line_idx;
        execute_line(program[cur_line_idx].text);
        if (running == 2) { running = 1; }   /* GOTO/GOSUB already set cur_line_idx */
        else if (running) cur_line_idx++;
    }
    running = 0;
}

/* ============================================================
   MAIN - READY loop
   ============================================================ */
int main() {
    srand((unsigned)time(NULL));
    printf("MS BASIC-80 C Port\nOk\n");
    char input[MAXBUF];
    while (1) {
        printf("> ");
        if (!fgets(input,MAXBUF,stdin)) break;
        input[strcspn(input,"\n")] = 0;
        if (!*input) continue;
        /* Check for line number */
        char *p = input;
        skip_ws(&p);
        if (isdigit(*p)) {
            int num = (int)strtol(p,&p,10);
            skip_ws(&p);
            insert_line(num, *p ? p : "");
        } else {
            /* Direct statement */
            if (strncasecmp(p,"RUN",3)==0) { collect_data(); data_pos=0; call_sp=0; for_sp=0; var_cnt=0; run_from(0); }
            else if (strncasecmp(p,"LIST",4)==0) { for(int i=0;i<prog_cnt;i++) printf("%d %s\n",program[i].num,program[i].text); }
            else if (strncasecmp(p,"NEW",3)==0) { prog_cnt=0; var_cnt=0; call_sp=0; for_sp=0; data_count=0; }
            else execute_stmt(p);
        }
        printf("Ok\n");
    }
    return 0;
}