《数据结构》中表达式求值的经典算法是用两个栈，一个存数字，一个存运算符。依次读入表达式中的每个字符，若是数字则进数字栈，若是运算符则和运算符栈的栈顶运算符比较优先权作相应操作，直至整个表达式求值完毕。运算符的优先级表如下

	+	-	*	/	(	)	#
+	>	>	<	<	<	>	>
-	>	>	<	<	<	>	>
*	>	>	>	>	<	>	>
/	>	>	>	>	<	>	>
(	<	<	<	<	<	=
)	>	>	>	>		>	>
#	<	<	<	<	<		=

  学了编译原理后，发现可以用递归下降分析来求表达式的值。表达式的文法如下

<Expr>    ->  <Term> { (+|-) <Term> }

<Term>   ->  <Factor> { (*|/) <Factor> }

<Factor>  ->  (<Expr>) | num

按照递归下降分析的技巧，每一个非终结符写一个函数

#pragma once#include
      
       using namespace std;/************************************************************************//*文法如下
       
            ->  
        
          { (+|-) 
         
           }
          
              ->  
           
             { (*|/) 
            
              }
             
               -> (
              
               ) | num/************************************************************************/class Calculator{public: Calculator(string &str); ~Calculator(); double calculate() { return ans; } double ans; //表达式的值private: int cur; //目前的位置 string str; double expression(); double term(); double factor();};
              
             
            
           
          
         
        
       
      

#include "Calculator.h"#include
      
       Calculator::Calculator(string & str) :str(str),cur(0),ans(0){    ans = expression();}Calculator::~Calculator(){}double Calculator::expression(){    double num1 = term();    double num2;    while (str[cur] == '+' || str[cur] == '-')    {        char op = str[cur++];    //运算符        num2 = term();        if (op == '+')    num1 += num2;        else if (op == '-')    num1 -= num2;    }    if (str[cur] == ')')    ++cur;    //factor遇到'('会调用此函数，因此要吃掉')'    return num1;}double Calculator::term(){    double num1 = factor();    double num2;    while (str[cur] == '*' || str[cur] == '/')    {        char op = str[cur++] ;        num2 = factor();        if (op == '*')    num1 *= num2;        else if (op == '/')    num1 /= num2;    }    return num1;}double Calculator::factor(){    char tmp = str[cur];    double result = tmp - '0';    ++cur;    if (tmp == '(')        return expression();    else    {
     //取数字        int flag = 0;//0为小数点之前，1位小数点之后        double temp = 10;        while (str[cur] >= '0' && str[cur] <= '9' || str[cur]=='.')        {            if (str[cur] == '.')            {                ++cur;                flag = 1;            }            else            {                if (!flag)//小数点之前                    result = result * 10 + str[cur] - '0';                else                {                    result = result + double(str[cur] - '0') / temp;                    temp *= 10;                }                ++cur;            }        }                return result;    }}
      

 

 main函数

#include 
     
      #include "Calculator.h"using namespace std;int main(){    string str;    cin >> str;    Calculator cal(str);    cout << cal.calculate() << endl;}
     

运行结果：