0001 const char* Prio = //将9x9的优先级表（右），压缩为长度为347的完美散列表（左）
0002       "~<  >   >  >       < .   >     <"     //       当  前  运  算  符
0003       " <  .>   >      >        <>     "     //        + - * / ^ ! ( ) $
0004       "    .   >< <           >    x< <"     // 栈 +:  > > < < < < < > >
0005       "         >    <        >  >  < <"     //    -:  > > < < < < < > >
0006       " . >   >      >  <   <   <      "     // 顶 *:  > > > > < < < > >
0007       "  .<  >< < <        >   <       "     //    /:  > > > > < < < > >
0008       "x   >  >>  >         >  >  <    "     // 运 ^:  > > > > > < < > >
0009       "            >< <   >   >      <<"     //    !:  > > > > > > x > >
0010       ". <   >           .  >      ~ < "     // 算 (:  < < < < < < < ~ x
0011       "  > .>>            >  ><        "     //    ):  . . . . . . . . .
0012       " .   x   <<<           >  <";         // 符 $:  < < < < < < < x ~
0013 char prio(char t, char c) { return Prio[(37*t + 47*c) % 347]; } //经散列，判定t与c的相对优先级
0014 double evaluate(char* S, char* RPN) { //对表达式S求值，并转换为RPN
0015    Stack<double> opnd;  Stack<char> optr; //运算数栈、运算符栈
0016    for (optr.push('\0'); !optr.empty(); ) //哨兵'\0'入栈，然后顺序扫描
0017       if (isdigit(*S)) //遇到操作数，则读入，并续接至RPN
0018          { readNumber(S, opnd);  append(RPN, opnd.top()); }
0019       else //若遇到运算符c = *S，则
0020          switch (prio(optr.top(), *S)) { //视栈顶运算符t与c的相对优先级，分别处理
0021             case '<': //t优先级更低时
0022                optr.push(*S);  S++; //计算推迟，c进栈
0023                break;
0024             case '>': //t优先级更高时
0025                append(RPN, optr.top()); //t续接至RPN，执行计算并令
0026                opnd.push(calcu(opnd, optr.pop())); //计算结果入栈（calcu()请自行实现）
0027                break;
0028             case '~': //t与c为一对括号或哨兵'\0'
0029                optr.pop();  S++; //脱括号并转至下一字符
0030                break;
0031          } //switch
0032    return opnd.pop(); //唯一尚存的操作数，即为计算结果
0033 } //evaluate：请自行扩充该算法，使之可以识别并处理非法的表达式