问题
输入一个中缀表达式，包括+，-，*，/，(，) 的四则运算，求其计算结果
例如：表达式((3+5*2)+3)/5+6/4*2+3的结果为8
分析
人生中第一场春招cvte的笔试题，简化后的四则表达式求值。也算是中规中距的一道编程题。考察编程基础，栈的使用。表达式求值是栈结构的延迟缓冲的应用。线性扫描算法模式中，在预读足够长之后，方能确定可处理的前缀
中缀表达式，最符合人们思维方式的一种表达式，操作符在操作数的中间。它的实现，需要两个栈：操作数栈和运算符栈。其中操作数栈用于保存当前计算值，运算符栈用于处理优先级问题。
后缀表达式，也称逆波兰表达式。不使用括号，即可表示带优先级的运算关系
。它由运算符出现的先后次序，来决定运算的前后。不需要考虑优先级的问题，计算机处理起来便简单很多
各编译器对四则运算表达式求值的实现也大同小异。基本思路都是，先将中缀转后缀，然后利用逆波兰表达式进行运算。一个栈即可搞定，简洁，高效。
优先级的处理，利用枚举的特性，通过字符二维数组，存放两运算符比较的运算结果。注意枚举的写法，还可以这样玩。
#define N_OPTR 9 //运算符总数
typedef enum { ADD, SUB, MUL, DIV, POW, FAC, L_P, R_P, EOE } Operator; //运算符集合
const char pri[N_OPTR][N_OPTR] = { //运算符优先等级 [栈顶] [当前]
/* |-------------------- 当 前 运 算 符 --------------------| */
/* + - * / ^ ! ( ) \0 */
/* -- + */ '>', '>', '<', '<', '<', '<', '<', '>', '>',
/* | - */ '>', '>', '<', '<', '<', '<', '<', '>', '>',
/* 栈 * */ '>', '>', '>', '>', '<', '<', '<', '>', '>',
/* 顶 / */ '>', '>', '>', '>', '<', '<', '<', '>', '>',
/* 运 ^ */ '>', '>', '>', '>', '>', '<', '<', '>', '>',
/* 算 ! */ '>', '>', '>', '>', '>', '>', ' ', '>', '>',
/* 符 ( */ '<', '<', '<', '<', '<', '<', '<', '=', ' ',
/* | ) */ ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ',
/* -- \0 */ '<', '<', '<', '<', '<', '<', '<', ' ', '='
};
Operator optr2rank ( char op ) { //由运算符转译出编号
switch ( op ) {//无需break,直接返回
case '+' : return ADD; //加
case '-' : return SUB; //减
case '*' : return MUL; //乘
case '/' : return DIV; //除
case '^' : return POW; //乘方
case '!' : return FAC; //阶乘
case '(' : return L_P; //左括号
case ')' : return R_P; //右括号
case '\0': return EOE; //起始符与终止符
default : exit ( -1 ); //未知运算符
}
}
char orderBetween ( char op1, char op2 ) //比较两个运算符之间的优先级
{ return pri[optr2rank ( op1 ) ][optr2rank ( op2 ) ]; }
按特定地格式将操作数接至RPN末尾，由中序得到后序表达式
void append ( char*& rpn, float opnd ) { //将操作数接至RPN末尾
//strlen函数返回字符串的长度
int n = strlen ( rpn ); //RPN当前长度（以'\0'结尾，长度n + 1）
char buf[64];
if ( opnd != ( float ) ( int ) opnd )
//sprintf的作用是将一个格式化的字符串输出到一个目的字符串中
sprintf ( buf, "%.2f \0", opnd ); //浮点格式，或
else
sprintf ( buf, "%d \0", ( int ) opnd ); //整数格式
//重新分配内存时，记得给结束符分配一个单元的空间
rpn = ( char* ) realloc ( rpn, sizeof ( char ) * ( n + strlen ( buf ) + 1 ) ); //扩展空间
strcat ( rpn, buf ); //RPN加长
}
char*& rpn 指针的引用，指针引用作为形参时，改变形参的指针，同时实参的指针也发生改变；char* rpn 改变形参的指针，实参的指针不改变
sprintf函数每次读取操作数放入buf数组中，并在操作数后面添加空格和结束符。strcat连接rpn和buf两个字符串，使用时需要注意，不要超过dest数组的大小
剔除输入字符串中的白空格。简化运算过程中，入栈时对空白字符检查操作
char* removeSpace ( char* s ) { //剔除s[]中的白空格
char* p = s, *q = s;
while ( true )
{
while ( isspace ( *q ) ) q++;
if ( '\0' == *q )
{
*p = '\0';
return s;
}
*(p++) = *(q++);
}
}
指针q跳过空格，将字符不断复制到指针p，通过p，q将相应位置上的内存内容修改，所以最终只需返回s即可
解析字符中的数字(整数或浮点数)，并存入操作数栈
void readNumber ( char*& p, Stack<float>& stk ) //p为指针引用，stk为引用
{ //将起始于p的子串解析为数值，并存入操作数栈
stk.push ( ( *p - '0' ) ); //当前数位对应的数值进栈
while ( isdigit ( * ( ++p ) ) ) //只要后续还有紧邻的数字（即多位整数的情况），则
{
int top = stk.top();
stk.pop();
stk.push ( top * 10 + ( *p - '0' ) ); //弹出原操作数并追加新数位后，新数值重新入栈
}
if ( '.' != *p ) return; //此后非小数点，则意味着当前操作数解析完成
float fraction = 1; //否则，意味着还有小数部分
while ( isdigit ( * ( ++p ) ) ) //逐位加入
{
float top = stk.top(); //top值为float型
stk.pop();
stk.push ( top + ( *p - '0' ) * ( fraction /= 10 ) ); //小数部分
}
}
%.2f 格式符，只取小数点后2位有效数字，不够补0。
float小数点前后加起来有效数字共6位；double小数前后加起来的有效数字共16位
中序表达式求值，并实现中缀转后缀
float evaluate(char *S, char *&RPN)
{
stack<float> opnd; stack<char> optr;
optr.push('\0'); //尾哨兵'\0'也作为头哨兵首先入栈，使得‘\0’与括号的处理方式统一起来
while (!optr.empty())//在运算符栈非空之前，逐个处理表达式中各字符
{
if (isdigit(*S))
{
readNumber(S, opnd); //读取数字
append_opnd(RPN, *S);
}
else
{
switch (orderBetween(optr.top(), *S)) //栈顶运算符与当前运算符之间优先级高低分别处理
{
case '<' :
optr.push(*S);
S++;
break;
case '=' :
optr.pop();
S++;
break;
case '>' : //当前运算符，并不急着入栈。与后序栈顶不断比较
{
char op = optr.top(); optr.pop();
append_optr(RPN, op); //将高优先级的栈顶运算符加入RPN中
if(*S == '!')//一元运算符
{
float Opnd = opnd.top(); opnd.pop();
calcu1(Opnd, op);
}
else//二元运算符
{
float Opnd1 = opnd.top(); opnd.pop();
float Opnd2 = opnd.top(); opnd.pop();
calcu2(Opnd1, op, Opnd2);
}
}
break;
default: //语法错误，直接-1退出
exit(-1);
}
}
}
return opnd.top();
}
optr.push('\0');尾哨兵’\0’也作为头哨兵首先入栈，使得‘\0’与括号的处理方式统一起来；求值过程的终止条件，运算符栈非空之前，逐个处理表达式中各字符；case:'>'当前运算符，并不急着入栈，与后序栈顶不断比较。
中缀转后缀的两个时机
if (isdigit(*S))
{
readNumber(S, opnd); //读取数字
append_opnd(RPN, *S);
}
append_optr(RPN, op); //将高优先级的栈顶运算符加入RPN中
C++语法小知识
realloc函数重新分配内存空间，ptr为需要重新分配的内存空间指针，size为新的内存空间的大小。
void* realloc (void* ptr, size_t size);
sprintf将一个格式化的字符串输出到一个目的字符串中；snprintf可以认为是sprintf()的升级版，比sprintf()多了一个参数，能够控制要写入的字符串的长度，更加安全，只要稍加留意，不会造成缓冲区的溢出。
优先级小问题
char *s = "ab";
cout << *s++ << endl; //++的优先级大于*，输出a
cout << *s << endl;//输出b
case语句含语句块的写法，使得代码结构更加清晰。
case '>' :{} break;