ソフトウェアエンジニアの技術ブログ：Software engineer tech blog

/**************************************/
/*  filename:bbi.h 共通ヘッダ           */
/**************************************/
#include <iostream>
#include <fstream>
#include <sstream>
#include <string>
#include <vector>
#include <stack>

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cctype>

using namespace std;

/* ---------------- define */
#define SHORT_SIZ sizeof(short int)
#define SHORT_P(p) (short int *)(p)
#define UCHAR_P(p) (unsigned char *)(p)
#define LIN_SIZ 255

/* ---------------- enum struct etc */
enum TknKind {
    Lparen='(', Rparen=')', Lbracket='[', Rbracket=']', Plus='+', Minus='-',
    Multi='*', Divi='/', Mod='%', Not='!', Ifsub='?', Assign='=',
    IntDivi='\\', Comma=',', DblQ='"',
    Func=150, Var, If, Elif, Else, For, To, Step, While,
    End, Break, Return, Option, Print, Println, Input, Toint,
    Exit, Equal, NotEq, Less, LessEq, Great, GreatEq, And, Or,
    END_KeyList,
    Ident, IntNum, DblNum, String, Leter, Doll, Digit,
    Gvar, Lvar, Fcall, EofProg, EofLine, Others
};

struct Token {
    TknKind kind;
    string text;
    double dblVal;
    Token() { kind = Others; text=""; dblVal=0.0; }
    Token (TknKind k) { kind=k; text=""; dblVal=0.0; }
    Token (TknKind k, double d){ kind=k; text=""; dblVal=d; }
    Token (TknKind k, const string& s) { kind=k; text=s; dblVal=0.0; }
    Token (TknKind k, const string& s, double d){ kind=k; text=s; dblVal=d; }
};

enum SymKind { noId, varId, fncId, paraId };
enum DtType { NON_T, DBL_T };

struct SymTbl{
    string name;
    SymKind nmKind;
    char dtTyp;
    int aryLen;
    short args;
    int adrs;
    int frame;
    SymTbl() { clear(); }
    void clear() {
        name=""; nmKind=noId; dtTyp=NON_T;
        aryLen=0; args=0; adrs=0; frame=0;
    }
};

struct CodeSet{
    TknKind kind;
    const char *text;
    double dblVal;
    int symNbr;
    int jmpAdrs;
    CodeSet() { clear(); }
    CodeSet(TknKind k) { clear(); kind=k; }
    CodeSet(TknKind k, double d ){ clear(); kind=k; dblVal=d; }
    CodeSet(TknKind k, const char *s) { clear(); kind=k; text=s; }
    CodeSet(TknKind k, int sym, int jmp){
        clear(); kind=k; symNbr=sym; jmpAdrs=jmp;
    }
    void clear() { kind=Others; text=""; dblVal=0.0; jmpAdrs=0; symNbr=-1; }
};

struct Tobj {
    char type;
    double d;
    string s;
    Tobj() { type = '-'; d = 0.0; s = ""; }
    Tobj(double dt) { type = 'd'; d = dt; s = ""; }
    Tobj(const string& st){ type = 's'; d = 0.0; s= st; }
    Tobj(const char *st){ type = 's'; d= 0.0; s = st; }
};

class Mymemory{
private:
    vector<double> mem;
public:
    void auto_resize(int n){
        if (n >= (int)mem.size()) { n = (n/256 + 1) * 256; mem.resize(n); }
    }
    void set(int adrs, double dt){mem[adrs] = dt; }
    void add(int adrs, double dt){ mem[adrs] += dt; }
    double get(int adrs) { return mem[adrs]; }
    int size() { return (int)mem.size(); }
    void resize(unsigned int n){ mem.resize(n); }
};

構文解析ルーチンを利用して、小さな電卓プログラムをつくります。字句解析や式解析の基本手法が含まれています。

/*--------------------------------*/
/*   電卓プログラム　minicalc.cpp    */
/*--------------------------------*/
#include 
#include 
#include 
using namespace std;

enum TknKind {
    Print, Lparen, Rparen, Plus, Minus, Multi, Divi,
    Assign, VarName, IntNum, EofTkn, Others
};

struct Token {
    TknKind kind;
    int intVal;
    Token() { kind = Others; intVal = 0; }
    Token(TknKind k, int d=0) { kind = k; intVal = d; }
};

void input();
void statement();
void expression();
void term();
void factor();
Token nextTkn();
int nextCh();
void operate(TknKind op);
void push(int n);
int pop();
void chkTkn(TknKind kd);

#define STK_SIZ 20
int stack[STK_SIZ+1];
int stkct;
Token token;
char buf[80], *bufp;
int ch;
int var[26];
int errF;

int main()
{
    while(1){
        input();
        token = nextTkn();
        if (token.kind == EofTkn) exit(1);
        statement();
        if (errF) cout << " --err--\n";
    }
    return 0;
}

void input()
{
    errF = 0; stkct = 0;
    cin.getline(buf, 80);
    bufp = buf;
    ch = nextCh();
}

void statement()
{
    int vNbr;
    
    switch (token.kind){
        case VarName:
            vNbr = token.intVal;
            token = nextTkn();
            chkTkn(Assign); if (errF) break;
            token = nextTkn();
            expression();
            var[vNbr] = pop();
            break;
        case Print:
            token = nextTkn();
            expression();
            chkTkn(EofTkn); if (errF) break;
            cout << " " << pop() << endl;
            return;
        default:
            errF = 1;
    }
    chkTkn(EofTkn);
}

void expression()
{
    TknKind op;
    
    term();
    while (token.kind == Plus || token.kind==Minus){
        op = token.kind;
        token = nextTkn(); term(); operate(op);
    }
}

void term()
{
    TknKind op;
    
    factor();
    while(token.kind==Multi || token.kind==Divi){
        op = token.kind;
        token = nextTkn(); factor(); operate(op);
    }
}

void factor()
{
    switch (token.kind){
        case VarName:
            push(var[token.intVal]);
            break;
        case IntNum:
            push(token.intVal);
            break;
        case Lparen:
            token = nextTkn();
            expression();
            chkTkn(Rparen);
            break;
        default:
            errF = 1;
    }
    token = nextTkn();
}

Token nextTkn()
{
    TknKind kd = Others;
    int num;
    
    while(isspace(ch))
        ch = nextCh();
    if (isdigit(ch)){
        for (num=0; isdigit(ch); ch = nextCh())
            num = num*10 + (ch-'0');
        return Token(IntNum, num);
    }
    else if (islower(ch)){
        num = ch - 'a';
        ch = nextCh();
        return Token(VarName, num);
    }
    else {
        switch (ch){
            case '(': kd = Lparen; break;
            case ')': kd = Rparen; break;
            case '+': kd = Plus; break;
            case '-': kd = Minus; break;
            case '*': kd = Multi; break;
            case '/': kd = Divi; break;
            case '=': kd = Assign; break;
            case '?': kd = Print; break;
            case '\0': kd = EofTkn; break;
        }
        ch = nextCh();
        return Token(kd);
    }
}

int nextCh()
{
    if (*bufp == '\0') return '\0'; else return *bufp++;
}

void operate(TknKind op)
{
    int d2 = pop(), d1 = pop();
    
    if (op==Divi && d2==0) { cout << " division by 0\n"; errF = 1; }
    if(errF) return;
    switch (op){
        case Plus: push(d1+d2); break;
        case Minus: push(d1-d2); break;
        case Multi: push(d1*d2); break;
        case Divi: push(d1/d2); break;
    }
}

void push(int n)
{
    if (errF)return;
    if (stkct+1 > STK_SIZ) { cout << "stack overflow\n"; exit(1); }
    stack[++stkct] = n;
}

int pop()
{
    if (errF) return 1;
    if (stkct < 1) { cout << "stack underflow\n"; exit(1); }
    return stack[stkct--];
}

void chkTkn(TknKind kd)
{
    if (token.kind != kd) errF = 1;
}

aからzまでの文字変数名と、一桁の数字を入力できます。

/*--------------------------------*/
/* 逆ポーランド記法の評価polish_p.cpp */
/*--------------------------------*/
#include 
#include 
#include 
using namespace std;

void polish(char *s);
int execute();
int getvalue(int ch);
int order(int ch);
void push(int n);
int pop();

#define STK_SIZ 20
int stack[STK_SIZ+1];
int stkct;
char plsh_out[80];

int main()
{
    char siki[80];
    int ans;
    
    cout << "入力:"; cin.getline(siki, 80);
    polish(siki);
    if (plsh_out[0] == '\n') exit(1);
    ans = execute();
    cout << "変換:" << plsh_out << endl;
    cout << "結果:" << ans << endl;
    return 0;
}

void polish(char *s)
{
    int wk;
    char *out = plsh_out;
    
    stkct = 0;
    for(;;) {
        while (isspace(*s)){ ++s; }
        if (*s == '\0'){
            while (stkct > 0){
                if ((*out++ = pop()) == '('){
                    puts("'('が不正\n"); exit(1);
                }
            }
            break;
        }
        if (islower(*s) || isdigit(*s)){
            *out++ = *s++; continue;
        }
        switch(*s) {
                case '(':
                push(*s);
                break;
                case ')':
                while ((wk = pop()) != '('){
                    *out++ = wk;
                    if(stkct == 0){ puts("'('が不足\n"); exit(1);}
                }
                break;
            default:
                if (order(*s) == -1){
                    cout << "不正な文字: " << *s << endl; exit(1);
                }
                while (stkct>0 && (order(stack[stkct]) >= order(*s))){
                    *out++ = pop();
                }
                push(*s);
        }
        s++;
    }
    *out = '\0';
}

int execute()
{
    int d1, d2;
    char *s;
    
    stkct = 0;
    for(s=plsh_out; *s; s++){
        if(islower(*s))
            push(getvalue(*s));
        else if (isdigit(*s))
            push(*s - '0');
        else {
            d2 = pop(); d1 = pop();
            switch(*s){
                case '+': push(d1+d2); break;
                case '-': push(d1-d2); break;
                case '*': push(d1*d2); break;
                case '/': if (d2 == 0){ puts("ゼロ除算"); exit(1); }
                    push(d1/d2); break;
            }
        }
    }
    if (stkct != 1){ cout << "ERROR\n"; exit(1); }
    return pop();
}

int getvalue (int ch)
{
    if (islower(ch)) return ch-'a' + 1;
    return 0;
}

int order(int ch)
{
    switch (ch){
        case '*': case '/': return 3;
        case '+': case '-': return 2;
        case '(': return 1;
    }
    return -1;
}

void push(int n)
{
    if (stkct+1 > STK_SIZ) { puts("stack overflow"); exit(1); }
    stack[++stkct] = n;
}

int pop()
{
    if (stkct < 1){ puts("stack underflow"); exit(1); }
    return stack[stkct--];
}