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的优先级低于c，则
0022                optr.push(*S);  S++; //计算推迟，c进栈
0023                break;
0024             case '>': //若t的优先级高于c，则
0025                append(RPN, optr.top()); //t续接至RPN；从opnd栈中取出运算数，执行t对应的运算，并
0026                opnd.push(calcu(opnd, optr.pop())); //将计算结果压入opnd栈（calcu()请自行实现）
0027                break;
0028             case '~': //若c为左括号、t为右括号，或者c为预埋的哨兵'\0'，t为表达式末尾的'\0'，则
0029                optr.pop();  S++; //消去括号或'\0'，并转至下一字符
0030                break;
0031          } //switch
0032    return opnd.pop(); //唯一尚存的操作数，即为计算结果
0033 } //evaluate：请自行扩充该算法，使之可以识别并处理非法的表达式