首页 > 代码库 > 简单算术表达式的求值程序

简单算术表达式的求值程序

2024-07-04 14:57:07   225人阅读

题目：
写一个三则运算(加减乘)表达式的求值程序，为了简化，规定数字只有一位，表达式内没有空格，但允许有括号。满足四则运算的结合性和优先级。

解答：
这是一道编译原理题，题目的要求把词法分析简单化了，只做语法分析。一般使用递归下降法求解。
首先写出BNF（包括结合性和优先权）。
exp → exp addop term | t e r m
addop → + | -
term → term mulop factor | f a c t o r
mulop → *
factor → ( exp ) | number
相对应的EBNF是
exp → t erm { addop term }
addop → + | -
term → factor { mulop factor }
mulop → *
factor → ( exp ) | number

可以看出EBNF从exp下降到term，再下降到factor，然后递归回到exp。这就是递归下降法名字的由来。

然后对应EBNF直接编码，可以看出错误检测的代码并没有反映在上面的表示中：

int factor(const char*& txt);
int term(const char*& txt);
int exp(const char*& txt)
{
                 int v = term(txt);
                 while (*txt)
                {
                                 if ( *txt == ‘+‘ )
                                {
                                                ++txt;
                                                 int v2 = term(txt);
                                                v += v2;
                                }
                                 else if ( *txt == ‘-‘ )
                                {
                                                ++txt;
                                                 int v2 = term(txt);
                                                v -= v2;
                                }
                                 else
                                {
                                                 break ;
                                }
                }
                 return v;
}

int term(const char*& txt)
{
                 int v = factor(txt);
                 while (*txt)
                {
                                 if ( *txt == ‘*‘ )
                                {
                                                ++txt;
                                                 int v2 = term(txt);
                                                v *= v2;
                                }
                                 else
                                {
                                                 break ;
                                }
                }
                 return v;
}

int factor(const char*& txt)
{
                 if (isdigit(*txt))
                {
                                 int v = *txt - ‘0‘ ;
                                ++txt;
                                 return v;
                }
                 else if (*txt == ‘(‘)
                {
                                ++txt;
                                 int v = exp(txt);
                                 if (*txt == ‘)‘ )
                                {
                                                ++txt;
                                                 return v;
                                }
                                 else
                                                 throw "invalid expression" ;
                }
                 else
                {
                                 throw "invalid expression" ;
                }
}

int calculate(const char* txt)
{
                 if (txt == nullptr )
                                 throw "invalid expression" ;
                 int v = exp(txt);
                  // this is necessary, or 3+4)*5 will be a valid expression.
                   if (*txt)
                                 throw "invalid expression" ;
                 return v;
}

/* Driver program to test above function */
int main()
{
                cout << calculate( "3" ) << endl;
                cout << calculate( "3*4" ) << endl;
                cout << calculate( "3+4" ) << endl;
                cout << calculate( "3+4*5" ) << endl;
                cout << calculate( "(3+4)*5" ) << endl;
                cout << calculate( "3*4+5" ) << endl;
                 try
                {
                                cout << calculate( "(3+4*5" ) << endl;
                }
                 catch (const char* e)
                {
                                cout << e << endl;
                }
                 try
                {
                                cout << calculate( "3+4)*5" ) << endl;
                }
                 catch (const char* e)
                {
                                cout << e << endl;
                }
                 try
                {
                                cout << calculate( "3*4+" ) << endl;
                }
                 catch (const char* e)
                {
                                cout << e << endl;
                }
                 try
                {
                                cout << calculate( "3*4+x" ) << endl;
                }
                 catch (const char* e)
                {
                                cout << e << endl;
                }
                 try
                {
                                cout << calculate( "" ) << endl;
                }
                 catch (const char* e)
                {
                                cout << e << endl;
                }
                 return 0;
}


联系
我们