C言語関係掲示板

過去ログ

No.455.中置記法

[戻る] [ホームページ]
No.3270

中置記法
投稿者---神奈川在住の人(2002/11/01 05:21:17)


逆ポーランド記法などのプログラムは良く見かけるのですが、
中置記法のって見ませんよね…
「スタックを使って中置式を読み込むと、その式の値を計算するプログラム」
はどのようにしたら実現できるでしょうか…。
どなたか教えてください。


No.3272

Re:中置記法
投稿者---aki(2002/11/01 09:59:35)


スタックは使ってないのですが、こんなのはどうでしょうか。
再起下降(recursive descent)という方法を使っています。

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

void error(const char *emsg) { fprintf(stderr, "%s", emsg), exit(1); }

typedef enum {
    NUMBER, PRINT, END, BAD_TOKEN,

    PLUS = '+', MINUS = '-', MUL = '*', DIV = '/', 
    LP = '(', RP = ')',
} Token_type;

int value;
Token_type token;

Token_type gettok(void)
{
    int c;

    while (isspace(c = getchar()) && c != '\n')
        ;

    switch (c) {
    case '\n':
        return token = PRINT;
    case EOF:
        return token = END;
    case '+':
    case '-':
    case '*':
    case '/':
    case '(':
    case ')':
        return token = c;
    default:
        if (isdigit(c)) {
            ungetc(c, stdin);
            scanf("%d", &value);
            return token = NUMBER;
        }
        return token = BAD_TOKEN;
    }
}

int expr(void);

int prime(void)
{
    switch (gettok()) {
        int e;
    case NUMBER:
        return value;
    case '(':
        e = expr();
        if (token != ')')
            error("括弧が閉じていません");
        return e;
    default:
        error("Bad token\n");
    }
}

int term(void)
{
    int left = prime();

    for (;;)
        switch (gettok()) {
        case '*':
            left *= prime();
            break;
        case '/':
            left /= prime();
            break;
        default:
            return left;
        }
}

int expr(void)
{
    int left = term();

    for (;;)
        switch (token) {
        case '+':
            left += term();
            break;
        case '-':
            left -= term();
            break;
        default:
            return left;
        }
}

int main(void)
{
    for (;;)
        printf("%d\n", expr());
    return 0;
}


No.3275

Re:中置記法
投稿者---aki(2002/11/01 12:38:15)


>再起下降(recursive descent)という方法を使っています。
再起ではなく再帰でした。

No.3329

Re:中置記法
投稿者---かずま(2002/11/05 01:07:28)


> スタックは使ってないのですが、こんなのはどうでしょうか。
> 再起下降(recursive descent)という方法を使っています。

この aki さんのプログラムですが、次のようなバグがあります。

3)5 を入力すると、3 が表示される。
3(5 を入力すると、5 が表示される。

No.3345

Re:中置記法
投稿者---aki(2002/11/06 09:27:20)


ご指摘ありがとうございます。
expr関数を次のように修正すればとれるようです。

int expr(void)
{
    int left = term();

    for (;;)
        switch (token) {
        case '+':
            left += term();
            break;
        case '-':
            left -= term();
            break;
        case PRINT:
            return left;
        default:
            error("syntax error\n");
        }
}


No.3283

Re:中置記法
投稿者---かずま(2002/11/01 21:46:45)


> 「スタックを使って中置式を読み込むと、その式の値を計算するプログラム」

再帰呼び出しで、暗にスタックは使っているんですがねえ。
#include <stdio.h>
#include <ctype.h>
#include <stdlib.h>

int c;  char b[1024], *p, o[] = "+-*/";

int g(void) { do c = *p++ & 0xff; while (isspace(c)); return c; }

double e(const char *s)
{
    double v;
    if (*s)
        for (v = e(s+2); c == s[0] || c == s[1]; )
            switch (c) {
            case '+': v += e(s+2); break;
            case '-': v -= e(s+2); break;
            case '*': v *= e(s+2); break;
            case '/': v /= e(s+2); break;
            }
    else if (g() == '(')
        v = e(o), c == ')' ? g() : (c = 1);
    else if (isdigit(c) || c == '.')
        v = strtod(p-1, &p), g();
    else
        v = c = 1;
    return v;
}

int main()
{
    double v;
    while (fgets(p = b, sizeof b, stdin))
        v = e(o), printf(c ? "  syntax error\n" : "  %.15g\n", v);
    return 0;
}


No.3284

Re:中置記法
投稿者---かずま(2002/11/01 22:17:26)


ちょっと、遊んでみました。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <math.h>

int c;  char b[1024], *p, o[] = "+-*/^ ";

int g(void) { do c = *p++ & 0xff; while (isspace(c)); return c; }

double e(const char *s)
{
    double v;
    if (*s)
        for (v = e(s+2); c == s[0] || c == s[1]; )
            switch (c) {
            case '+': v += e(s+2); break;
            case '-': v -= e(s+2); break;
            case '*': v *= e(s+2); break;
            case '/': v /= e(s+2); break;
            case '^': v = pow(v, e(s));
            }
    else if (g() == '(')
        v = e(o), c == ')' ? g() : (c = 1);
    else if (c == '-')
        v = -e(s);
    else if (c == '+')
        v = e(s);
    else if (isdigit(c) || c == '.')
        v = strtod(p-1, &p), g();
    else if (!memcmp(p-1, "sqrt", 4))
        p += 3, v = sqrt(e(s));
    else if (!memcmp(p-1, "exp", 3))
        p += 2, v = exp(e(s));
    else if (!memcmp(p-1, "log", 3))
        p += 2, v = log(e(s));
    else if (!memcmp(p-1, "sin", 3))
        p += 2, v = sin(e(s));
    else if (!memcmp(p-1, "cos", 3))
        p += 2, v = cos(e(s));
    else if (!memcmp(p-1, "tan", 3))
        p += 2, v = tan(e(s));
    else if (!memcmp(p-1, "atan", 4))
        p += 3, v = atan(e(s));
    else
        v = c = 1;
    return v;
}

int main()
{
    double v;
    while (fgets(p = b, sizeof b, stdin))
        v = e(o), printf(c ? "  syntax error\n" : "  %.15g\n", v);
    return 0;
}
----------------------------------------------------------------------
実行例

355/113
  3.14159292035398
sqrt(2)
  1.4142135623731
exp(1)
  2.71828182845905
4 * atan(1)
  3.14159265358979
sin(1)^2 + cos(1)^2
  1
^Z


No.3285

Re:中置記法
投稿者---神奈川在住の人(2002/11/02 00:20:21)


あ、すごい…。
ありがとうございます。
さっそく試してみます。本当に感謝です。

No.3286

Re:中置記法
投稿者---神奈川在住の人(2002/11/02 00:27:28)


なんか、目に見えるスタックを使うと
とてつもなくめんどくさい…と思うんですけど
それが課題みたいです。
ああ、どうなんでしょう。
しかも、配列を使ったスタック…らしいです。
全然わかりません…。
どうにかなりませんか…

No.3294

Re:中置記法
投稿者---かずま(2002/11/02 22:34:17)


数値スタックと、演算子スタックの 2つのスタックを使ってみました。
バグがあるかもしれません。ご指摘ください。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

double  val_stack[32]; int vi;
int     op_stack[32];  int oi;
char    buf[1024], *bp, c;

void push_val(double v) {
    if (vi >= 32) puts("val_stack overflow"), exit(1); val_stack[vi++] = v; }
double pop_val(void) { return val_stack[--vi]; }

void push_op(int o) {
    if (oi >= 32) puts("op_stack overflow"), exit(1); op_stack[oi++] = o; }
int pop_op(void)  { return op_stack[--oi]; }

int get(void) { do { c = *bp++ & 0xff; } while (isspace(c)); return c; }

int precedence(int op)
{
    switch (op) {
    default:            return 0;
    case '(': case ')': return 1;
    case '+': case '-': return 2;
    case '*': case '/': return 3;
    }
}
    
int expr(void)
{
    oi = vi = 0; push_op(1);
    for (;;) {
        if (get() == '(') 
            push_op(c);
        else if (isdigit(c) || c == '.') {
            int op;
            push_val(strtod(bp-1, &bp));
            if (get() && !strchr("()+-*/", c)) 
                return puts("  unkonwn operator"), 0;
            while (precedence(op = pop_op()) >= precedence(c)) {
                if (op == 1) return 1;
                if (op == '(') {
                    if (c != ')') return puts("  parenthesis"), 0;
                    get();
                } else {
                    double val = pop_val();
                    switch (op) {
                    case '+': push_val(pop_val() + val); break;
                    case '-': push_val(pop_val() - val); break;
                    case '*': push_val(pop_val() * val); break;
                    case '/': push_val(pop_val() / val); break;
                    }
                }
            }
            push_op(op); push_op(c);
        } else return puts("  syntax error"), 0;
    }
}

int main()
{
    while (fgets(bp = buf, sizeof buf, stdin))
        if (expr()) printf("  %.15g\n", pop_val());
    return 0;
}


No.3299

Re:中置記法
投稿者---神奈川在住の人(2002/11/03 00:20:37)


わーお。
おりがとうございます。
早速試してみます。
大感謝です。

No.3302

Re:中置記法
投稿者---神奈川在住の人(2002/11/03 00:44:56)


おりがとうごさいます…になってる…。
すいません。
ありがとうございます。
試してみたのですが、
(1+1)*2=
とやってもできません…。
今解読中です。

No.3312

Re:中置記法
投稿者---かずま(2002/11/03 20:44:22)


> 数値スタックと、演算子スタックの 2つのスタックを使ってみました。
> バグがあるかもしれません。ご指摘ください。

やはり、バグがありました。

 if (get() && !strchr("()+-*/", c)) を
 if (get() && !strchr(")+-*/", c)) に訂正します。

こうしないと、1(2) が 2 になってしまいます。

No.3315

Re:中置記法
投稿者---神奈川在住の人(2002/11/03 22:33:19)


あ、なるほど…。
ありがとうございました。

No.3327

Re:中置記法
投稿者---かずま(2002/11/05 00:48:49)


>> 数値スタックと、演算子スタックの 2つのスタックを使ってみました。
>> バグがあるかもしれません。ご指摘ください。

> やはり、バグがありました。

さらに、バグが見つかりました。

 push_op(op); push_op(c); の前に、
 if (c == ')') return puts(" parenthesis"), 0; を追加してください。

こうしないと、1)2 がエラーになりません。

No.3350

Re:中置記法
投稿者---神奈川在住の人(2002/11/06 23:17:58)


ありがとうございます。
ほんとに感謝しております。


No.3355

Re:中置記法
投稿者---aki(2002/11/07 03:01:15)


いろいろ機能をつけた電卓を作ってみました。よかったら遊んでみて
ください。プログラム改善のアドバイスやバクの報告も歓迎します。

プログラムが長くなってしまったので二つに分けます。

実行例
-2 + 3 * (-4)      # コメントが書けます
-14
m * 2              # m は直前の計算結果
-28
2^8; 17 % 5;       # マルチステートメント
256
2
5!; |-2|; [7.2]    # 階乗  絶対値  ガウス記号
120
2
7
pi; e;             # 定数
3.14159
2.71828
2 (3 + 1) (7 - 5)  # * は省略できる場合もある
16
2 pi; 3[1-5]       # * の省略
6.28319
-12
pi 2; 3|-2|;       # * が省略できないケース
不正な構文
不正な構文
2 acos(0); cos(0); # 関数
3.14159
1
log(exp(123))
123
log10 1e+123
123
abs(-5)
5
fabs(-5)
5
pow(e, log pi)
3.14159
sqrt(m^2) "ans = %+.15f"   # 書式指定
ans = +3.141592653589793
;;;;;;;;;;;;;              # 空式
(3 + (-2 / (3 + 4)) + 2    # 的確なエラー表示
')' がない
^z

#include <stdio.h>
#include <ctype.h>
#include <math.h>
#include <setjmp.h>
#include <stdarg.h>
#include <string.h>

extern jmp_buf env;

void error(const char *fmt, ...)
{
    va_list ap;
    va_start(ap, fmt);
    vfprintf(stderr, fmt, ap);
    fputc('\n', stderr);
    va_end(ap);

    longjmp(env, 1);
}

typedef enum {
    NUMBER, NAME, PRINT, PRINTF, END, OTHER,

    HAT = '^', MUL = '*', DIV = '/', MOD = '%', PLUS = '+', MINUS = '-',
    LP = '(', RP = ')', LB = '[', RB = ']', COMMA = ',',
    SHARP = '#', EXCLAM = '!', ABS = '|', QUOTE = '"'
} Token_type;

#define NAME_MAX 20
#define FORMAT_MAX 200

Token_type  token, token_buf;
double      value, value_buf;
char        name[NAME_MAX], name_buf[NAME_MAX];
char        format[FORMAT_MAX];
int         buf_flg;

Token_type gettok(void)
{
    int c;

    if (buf_flg) {
        buf_flg = 0;
        value = value_buf;
        strcpy(name, name_buf);
        return token = token_buf;
    }

    while (isspace(c = getchar()) && c != '\n')
        ;

    if (c == '#')
        while ((c = getchar()) != EOF && c != '\n')
            ;

    if (c == '"') {
        int i = 0;
        while ((c = getchar()) != '"') {
            if (c == '\n') token = PRINT, error("\" が閉じていません");
            format[i++] = c;
            if (i == FORMAT_MAX) error("フォーマットが長すぎます");
        }
        format[i] = '\0';
        while ((c = getchar()) != '\n' && c != ';')
            ;
    }

    switch (c) {
    case EOF:
        return token = END;
    case '\n':
    case ';':
        return token = PRINT;
    case '^':
    case '*':
    case '/':
    case '%':
    case '+':
    case '-':
    case '(':
    case ')':
    case '[':
    case ']':
    case '|':
    case '!':
    case ',':
        return token = c;
    default:
        if (isdigit(c) || c == '.') {
            ungetc(c, stdin);
            if (scanf("%lf", &value) != 1)
                error("不正な浮動小数点数");
            return token = NUMBER;
        } else if (isalpha(c)) {
            ungetc(c, stdin);
            scanf("%[a-zA-Z0-9]", name);
            return token = NAME;
        }
        return token = OTHER;
    }
}

void un_gettok(void)
{
    buf_flg = 1;
    token_buf = token;
    value_buf = value;
    strcpy(name_buf, name);
}

void clear_un_gettok_buf(void) { buf_flg = 0; }

#define STACK_SIZE 256

double stack[STACK_SIZE];
int sp;
void push(double v)
{
    if (sp >= STACK_SIZE) error("stack overflow");
    stack[sp++] = v;
}
double pop(void) { return stack[--sp]; }

Token_type op_stack[STACK_SIZE];
Token_type op_sp;
void push_op(Token_type tk)
{
    if (op_sp >= STACK_SIZE) error("stack overflow");
    op_stack[op_sp++] = tk;
}
Token_type pop_op(void) { return op_stack[--op_sp]; }
Token_type top_op(void) { return op_stack[op_sp-1]; }
int get_op_sp(void) { return op_sp; }

void clear_stack(void) { sp = op_sp = 0; }


No.3356

Re:中置記法
投稿者---aki(2002/11/07 03:17:58)


続きです

void expect(Token_type check, Token_type exp)
{
    if (check != exp) error("'%c' がない", exp);
}

double expr(void);

void get2arg(double *a1, double *a2)
{
    expect(gettok(), '(' ); *a1 = expr();
    expect(token,    ',' ); *a2 = expr();
    expect(token,    ')' );
}

double prime(void);

double math_func(const char *n)
{
    double a1, a2;
    extern double memory;

    if (strcmp(n, "m"    ) == 0) return memory;
    if (strcmp(n, "pi"   ) == 0) return 2 * acos(0);
    if (strcmp(n, "e"    ) == 0) return exp(1);

    if (strcmp(n, "acos" ) == 0) return acos(prime());
    if (strcmp(n, "asin" ) == 0) return asin(prime());
    if (strcmp(n, "atan" ) == 0) return atan(prime());
    if (strcmp(n, "cos"  ) == 0) return cos(prime());
    if (strcmp(n, "sin"  ) == 0) return sin(prime());
    if (strcmp(n, "tan"  ) == 0) return tan(prime());
    if (strcmp(n, "exp"  ) == 0) return exp(prime());
    if (strcmp(n, "log"  ) == 0) return log(prime());
    if (strcmp(n, "log10") == 0) return log10(prime());
    if (strcmp(n, "sqrt" ) == 0) return sqrt(prime());
    if (strcmp(n, "ceil" ) == 0) return ceil(prime());
    if (strcmp(n, "fabs" ) == 0) return fabs(prime());
    if (strcmp(n, "abs"  ) == 0) return fabs(prime());
    if (strcmp(n, "floor") == 0) return floor(prime());

    if (strcmp(n, "pow"  ) == 0) return get2arg(&a1, &a2), pow(a1, a2);
    if (strcmp(n, "fmod" ) == 0) return get2arg(&a1, &a2), fmod(a1, a2);

    return error("未定義の名前です"), 0;
}

double prime_sub(void)
{
    switch (gettok()) {
        double v;
    case '+':
        return +prime();
    case '-':
        return -prime();
    case NUMBER:
        return value;
    case NAME:
        return math_func(name);
    case '|':
        v = expr();
        expect(token, '|');
        return fabs(v);
    case '[':
        v = expr();
        expect(token, ']');
        return floor(v);
    case '(': 
        v = expr();
        expect(token, ')');
        return v;
    default:
        return error("不正な構文"), 0;
    }
}

double prime(void)
{
    double n, v = prime_sub();

    if (gettok() == '!') {
        if (modf(v, &n) != 0.0 || n < 0)
            error("'!' のオペランドは0か自然数でなければならない");
        v = 1;
        while (n) v *= n--;
    } else
        un_gettok();
    return v;
}

void push_eval(double left, Token_type op, double right)
{
    switch (op) {
    case '^':
        push(pow(left, right));
        return;
    case '*':
        push(left * right);
        return;
    case '/':
        if (right == 0) error("0で割ろうとしました");
        push(left / right);
        return;
    case '%':
        if (right == 0) error("'%'演算子の右オペランドが0です");
        push(fmod(left, right));
        return;
    case '+':
        push(left + right);
        return;
    case '-':
        push(left - right);
        return;
    }
}

int levelof(Token_type op)
{
    switch (op) {
    default:                        return -1;
    case '+': case '-':             return  0;
    case '*': case '/': case '%':   return  1;
    case '^':                       return  2;
    }
}

double expr(void)
{
    int bottom = get_op_sp();

    for (;;) {
        push(prime());
        if (gettok() == NAME || token == '(' || token == '[') {
            un_gettok();
            token = '*';
        }
        while (bottom != get_op_sp() && levelof(token) <= levelof(top_op())) {
            double right = pop();
            double left  = pop();
            push_eval(left, pop_op(), right);
        }
        if (!strchr("^*/%+-", token) || token == 0)
            return pop();
        push_op(token);
    }
}

jmp_buf env;
double memory;

int main(void)
{
    for (;;) {
        if (!setjmp(env)) {
            if (gettok() == END) break;
            if (token == PRINT) continue;
            strcpy(format, "%g");
            un_gettok();
            memory = expr();
            if (token != PRINT) error("不正な構文");
            printf(format, memory); putchar('\n');
        } else {
            while (token != PRINT)
                gettok();
            clear_stack();
            clear_un_gettok_buf();
        }
    }
    return 0;
}