论坛 › C\C++交流 › 算术表达式求值(10以内整数)

柠檬Ccc 发表于 2022-4-29 17:21:07

算术表达式求值(10以内整数)

【问题描述】假设一算术表达式的所有操作数均为10以内的整数，请编写代码实现表达式求值。

假设算术表达式满足:

(1) 小括号已匹配；

(2) 表达式无除0错误;

(3) 表达式中间没有多余的空格。

要求： 表达式计算的中间值可以是负数或者实数

【输入形式】第一行输入表达式字符串
【输出形式】第二行输出计算结果（保留两位小数）
【样例输入】(4+1*(5-2))-6/3
【样例输出】5.00

人造人 发表于 2022-4-30 13:45:11

先贴代码
#include <stdio.h>
#include <stdbool.h>
#include <ctype.h>

enum {EMPTY = 256, ERROR, OK, NUM};

int symbol;
double value;

int symbol_;
double value_;

void back(void) {
    symbol_ = symbol;
    value_ = value;
}

void next(void) {
    if(symbol_ != 0) {
      symbol = symbol_;
      value = value_;
      symbol_ = 0;
      return;
    }
    symbol = getchar();
    switch(symbol) {
      case ' ':
      case '\t':
      case '\v':
      case '\f':
            return next();
    }
    if(!isdigit(symbol)) return;
    ungetc(symbol, stdin);
    int temp;
    scanf("%d", &temp);
    value = temp;
    symbol = NUM;
    return;
}

void factor(void) {
    next();
    if(symbol == NUM) return;
    if(symbol != '(') goto err;
    void expression(void);
    expression();
    if(symbol != NUM) goto err;
    double temp = value;
    next();
    if(symbol != ')') goto err;
    symbol = NUM;
    value = temp;
    return;
err:
    symbol = ERROR;
    return;
}

void term(void) {
    factor();
    if(symbol != NUM) goto err;
    double a = value;
    next();
    if(!(symbol == '*' || symbol == '/')) {
      back();
      symbol = NUM;
      value = a;
      return;
    }
    int op = symbol;
    term();
    if(symbol != NUM) goto err;
    value = op == '*' ? a * value : a / value;
    return;
err:
    symbol = ERROR;
    return;
}

void expression(void) {
    term();
    if(symbol != NUM) goto err;
    double a = value;
    next();
    if(!(symbol == '+' || symbol == '-')) {
      back();
      symbol = NUM;
      value = a;
      return;
    }
    int op = symbol;
    expression();
    if(symbol != NUM) goto err;
    value = op == '+' ? a + value : a - value;
    return;
err:
    symbol = ERROR;
    return;
}

void line(void) {
    next();
    if(symbol == '\n') return;
    back();
    expression();
    if(symbol == '\n') return;
    if(symbol != NUM) goto err;
    double a = value;
    next();
    if(symbol != '\n') goto err;
    printf(">>> %lf\n", a);
    return;
err:
    printf("错误的表达式!\n");
    symbol = ERROR;
    return;
}

void lines(void) {
    next();
    if(symbol == EOF) {
      symbol = OK;
      return;
    }
    back();
    line();
    //if(symbol == ERROR) return;
    return lines();
}

bool start(void) {
    lines();
    if(symbol != OK) return false;
    next();
    if(symbol != EOF) return false;
    return true;
}

int main(void) {
    start();
    return 0;
}


假设1. 小括号已匹配
我不做这个假设，如果括号不匹配，我写的这个程序会打印一个错误信息

假设3. 表达式中间没有多余的空格
要在程序中忽略这些多余的空格也不复杂呀，所以我写的这个程序依然不做这个假设

假设 所有操作数均为10以内的整数
这个假设没意思吧，就支持一位数字？你用scanf读取不就可以了

假设太多了，没意思

下面说一说这个代码的思路
1. 首先写出这个语言（表达式）的文法
start: lines (EOF);

lines: (EMPTY)
   | line lines
   ;

line: expression '\n' {print(expression);}
    | '\n'
    | (ERROR) {printf("错误的表达式!\n");}
    ;

expression: term
          | expression '+' term {$$ = $1 + $3;}
          | expression '-' term {$$ = $1 - $3;}
          ;

term: factor
    | term '*' factor {$$ = $1 * $3;}
    | term '/' factor {$$ = $1 / $3;}
    ;

factor: NUM
      | '(' expression ')' {$$ = $2;}
      ;

2. 消除左递归， 因为要使用递归下降分析
expression: term expression_;
expression_: (EMPTY)
         | '+' term expression_
         | '-' term expression_
         ;

term: factor term_;
term_: (EMPTY)
   | '*' factor term_
   | '/' factor term_
   ;
编译原理教材中用的是这种方法
但是，为什么不能改成这样？
expression: term
          | term '+' expression {$$ = $1 + $3;}
          | term '-' expression {$$ = $1 - $3;}
          ;

term: factor
    | factor '*' term {$$ = $1 * $3;}
    | factor '/' term {$$ = $1 / $3;}
    ;
这样也没有左递归呀，上面的那个代码用的就是这种方法，到目前为止还没有发现 有什么问题

3. 照着这个文法，用递归下降分析，写代码
4. 调试，^_^

查看完整版本: 算术表达式求值(10以内整数)