算术表达式求值

首先我们需要明确要解决的问题,它是对一个以字符串形式给出的算术表达式求值。尽管对算术表达式我们已经再熟悉不过了,不过仍然有许多细节值得注意,比如运算符操作数个数、数值类型等等。为简化问题,这里规定表达式中只出现常规形式的数值以及四则运算。
表达式形式化定义如下:

Expr ::= expr + expr
    | expr – expr
    | expr * expr
    | expr / expr
    | (expr)

显然这样的形式可以轻松地扩展到任意二元运算,我们的设计也力求满足易于扩展的要求。
我们通过实际经验以及数学知识可以知道,表达式可以依照运算的结合性构建出一棵二叉树,求值过程就是对这棵树进行(中)根序遍历的过程。由根序遍历的特点,可以选择栈结构来解决这个问题。

我们准备了两个栈,一个存储运算符(包括括号以及控制标志),一个存储操作数。依次读入表达式,根据运算符优先级,选择把操作数入栈暂存还是出栈运算。所有的操作完成我们就得到最终结果。

这里涉及到运算符优先级的问题,这与栈操作是相对应的。事实上,运算符间的优先关系不是简单的序关系,因为在有些情况下对称性并不成立。我们把操作符两两比较,有 < > =三种结果,对此可以用一个二数组来存储。

将运算符标识与数组下表对应起来,可以借助 std::map 实现,也可以直接定义为枚举类型并指定整数值。

我们要从表达式串中分离出操作数和运算符。可以对字符串进行一遍扫描,边解析边计算。不过这样不得不考虑很多问题。为简化思路,这里选择先从字符串中解析出所有Token 存起来,再直接使用token进行计算。

源程序

// EvaluateExpr.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <string>
#include <stack>
#include <sstream>

using namespace std;

enum optr_t {ADD=0, SUB, MUL, DIV, LP, RP, END};
typedef enum { OPTR, OPND } token_t;
typedef double opnd_t;

typedef struct {
    token_t type;
    opnd_t value;
    optr_t op;
} Token;

// 符号解析结果
Token tokens[100];
int ntoken = 0;

// 运算优先级表
char ops[] = { '+', '-', '*', '/', '(', ')', '#' };
char PrecedeTable[][7] = {
{'>', '>', '<', '<', '<', '>', '>'},
{'>', '>', '<', '<', '<', '>', '>'},
{'>', '>', '>', '>', '<', '>', '>'},
{'>', '>', '>', '>', '<', '>', '>'},
{'<', '<', '<', '<', '<', '=', ' '},
{'>', '>', '>', '>', ' ', '>', '>'},
{'<', '<', '<', '<', '<', ' ', '='}
};



// 执行计算
opnd_t Operate(opnd_t a, optr_t theta, opnd_t b);

// 词法分析
void ParseToken(std::string expr);

// 对词法分析结果求值
opnd_t Eval(Token* tokens);

// 求值程序测试
int Test();

// 查询优先级
char Precede(optr_t a, optr_t b)
{
    return PrecedeTable[a][b];
}

// 判断是否为数字
bool isDigit(char c)
{
    return c >= '0' && c <= '9';
}

// 判断是否为操作符
bool isOp(Token t)
{
    return t.type == OPTR;
}

// 从数值串中读出值
double parseValue(string token)
{
    double d;
    istringstream iss(token);
    iss >> d;
    return d;
}

void ERROR()
{
    cout << "ERROR: syntax invalid! " << endl;
    exit(-1);
}


/*======== 主函数入口 ========*/

int main() 
{
    int quit;
    do {
        quit = Test();
    } while (!quit);
    return 0;
}




/*==========  函数实现 ============*/


opnd_t Operate(opnd_t a, optr_t theta, opnd_t b)
{
    cout << "Operate: " << a << ops[theta] << b << endl;
    switch (theta) {
    case ADD:
        return a + b;
    case SUB:
        return a - b;
    case MUL:
        return a * b;
    case DIV:
        return a / b;
    default: 
        return -999999;
    }
}

void ParseToken(std::string expr)
{
    string stoken;
    string::iterator it1 = expr.begin();
    string::iterator it2;
    while (it1 != expr.end()) {
        if (isDigit(*it1)) {    // int
            it2 = it1 + 1;
            while (it2 != expr.end()) {
                if (!isDigit(*it2)) {
                    break;
                } //if
            } //while
            stoken.assign(it1, it2);
            cout << "Token NUM: " << stoken << endl;
            tokens[ntoken].type = OPND;
            tokens[ntoken].value = parseValue(stoken);
            ntoken++;
            it1 = it2;
        } //if
        else if (*it1 == ' ') { // skip spaces
            it1++;
        }
        else if (*it1 == '(') {    // LP
            cout << "Token LP: (" << endl;
            tokens[ntoken].type = OPTR;
            tokens[ntoken].op = LP;
            ntoken++;
            it1++;
        }
        else if (*it1 == ')') { // RP
            cout << "Token RP: " << ")" << endl;
            tokens[ntoken].type = OPTR;
            tokens[ntoken].op = RP;
            ntoken++;
            it1++;
        }
        else if (*it1 == '+') {    // ADD
            cout << "Token ADD: " << "+" << endl;
            tokens[ntoken].type = OPTR;
            tokens[ntoken].op = ADD;
            ntoken++;
            it1++;
        }
        else if (*it1 == '-') {    // SUB
            cout << "Token SUB: " << "-" << endl;
            tokens[ntoken].type = OPTR;
            tokens[ntoken].op = SUB;
            ntoken++;
            it1++;
        }
        else if (*it1 == '*') {    // MUL
            cout << "Token MUL: " << "*" << endl;
            tokens[ntoken].type = OPTR;
            tokens[ntoken].op = MUL;
            ntoken++;
            it1++;
        }
        else if (*it1 == '/') {    // DIV
            cout << "Token DIV: " << "/" << endl;
            tokens[ntoken].type = OPTR;
            tokens[ntoken].op = DIV;
            ntoken++;
            it1++;
        }
    } //while
    tokens[ntoken].type = OPTR;
    tokens[ntoken].op = END;    // END flag
    ntoken++;

}


opnd_t Eval(Token* tokens)
{
    Token c;
    optr_t theta;
    opnd_t a, b;
    std::stack<optr_t> optr;
    std::stack<opnd_t> opnd;
    optr.push(END);
    int i = 0;
    while (tokens[i].op != END || optr.top() != END) {
        c = tokens[i];
        if (!isOp(c)) {
            opnd.push(c.value);
            i++;
        }
        else {    // token c is of type OPTR
            switch (Precede(optr.top(), c.op)) {
            case '<':
                optr.push(c.op);
                i++;
                break;
            case '=': // 脱括号并接受下一字符
                optr.pop();
                i++;
                break;
            case '>':
                theta = optr.top(); optr.pop();
                b = opnd.top(); opnd.pop();
                a = opnd.top(); opnd.pop();
                opnd.push(Operate(a, theta, b));
                break;
            case ' ':
                ERROR();
                break;
            } // switch
        } // else
    } //while
    return opnd.top();
}


int Test()
{
    std::string expr;
    cout << "input an expression (q to quit): ";
    cin >> expr;
    if (expr[0] == 'q') return 1;
    ParseToken(expr);
    double res = Eval(tokens);
    cout << "the value of expr " << expr << " is: " << res << endl;
    return 0;
}