数据结构学习（栈与队列：五（延迟缓冲））

延迟缓冲

表达式求值

下面给出上一届代码中orderBetween（）函数与readNumber（）函数：

void readNumber(char*& p, Stack<float>& stk)
{ //将起始于p的子串解析为数值，并存入操作数栈
	stk.push((float) (*p - "0"));//当前数位对应的数值进栈
	while (isdigit(*(++p))) //只要后面还有紧邻的数字（即多位整数的情况），则
		stk.push(stk.pop*10 + (*p - "0")); //弹出原操作数并追加新数位后，新数值重新入栈
	if("." != *p) return; //此后非数点，则意味着当前操作数解析完成
	float fraction = 1;//否则，意味着还有小数部分
	while(isdigit(*(++p)))//逐位加入
		stk.push(stk.pop() + (*p - "0") * (fraction /= 10));//小数部分
}

关于orderBetween’函数，需要利用事先规定的优先级表：

#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)
	{
		case'+' : return ADD;//加
		case'-' : return SUB;//减
		case'*' : return ADD;//乘
		case'/' : return ADD;//除
		case'^' : return ADD;//乘方
		case'!' : return ADD;//阶乘
		case'(' : return ADD;//左括号
		case')' : return ADD;//右括号
		case'\0' : return ADD;//起始符与终止符
		default : exit(-1);//位置运算符
	}
}

char orderBetween(char op1, char op2)//比较两个操作符之间的优先级
{
	return pri[optr2rank(op1)][]optr2rank(op2)];
}