C++ 数据结构(四)栈与队列(2)栈应用(3)中缀表达式
     发布在:C/C++      浏览:38      评论:0 条评论

上一篇:《C++ 数据结构(四)栈与队列(2)栈应用(2)栈混洗与括号匹配》

典型应用场合

1、逆序输出(conversion)

输出次序与处理过程颠倒,递归深度和输出长度不易预知

2、递归嵌套(stack permutation + parenthesis)

具有自相似性的问题可递归描述,但分支位置和嵌套深度不固定

3、延迟缓冲(evaluation)

线性扫描算法模式中,在预读足够长之后,方能确定可处理的前缀

4、栈式计算(RPN)

基于栈结构的特定计算模式

表达式求值

给定语法正确的算术表达式 S,计算与之对应的数值

> echo $(( 0 + ( 1 + 23 ) / 4 * 5 * 67 - 8 + 9 ))
> set /a ( !0 ^<^< ( 1 - 2 + 3 * 4 ) ) - 5 * ( 6 ^| 7 ) / ( 8 ^^ 9 )

构思

C++ 数据结构(四)栈与队列(2)栈应用(3)中缀表达式

延迟缓冲

C++ 数据结构(四)栈与队列(2)栈应用(3)中缀表达式

实例

求值算法 = 栈 + 线性扫描

C++ 数据结构(四)栈与队列(2)栈应用(3)中缀表达式

实现:主算法

float evaluate(char *S, char *&RPN) { // 中缀表达式
    Stack<float> opnd; Stack<char> optr; // 运算数栈、运算符栈
    optr.push('
float evaluate(char *S, char *&RPN) { // 中缀表达式
Stack<float> opnd; Stack<char> optr; // 运算数栈、运算符栈
optr.push('\0'); // 尾哨兵 '\0' 也作为头哨兵首先入栈
while (!optr.empty()) { // 逐个处理各字符,直至运算符栈空
if (isDigit(*S)) // 若当前字符为操作数,则
readNumber(S, opnd); // 读入(可能多位的)操作数
else // 若当前字符为运算符,则视其与栈顶运算符之间优先级的高低
switch(orderBetween(optr.top(), *S)) { /* 分别处理 */ }
} // while
return opnd.pop(); // 弹出并返回最后的计算结果
}
'); // 尾哨兵 '
float evaluate(char *S, char *&RPN) { // 中缀表达式
Stack<float> opnd; Stack<char> optr; // 运算数栈、运算符栈
optr.push('\0'); // 尾哨兵 '\0' 也作为头哨兵首先入栈
while (!optr.empty()) { // 逐个处理各字符,直至运算符栈空
if (isDigit(*S)) // 若当前字符为操作数,则
readNumber(S, opnd); // 读入(可能多位的)操作数
else // 若当前字符为运算符,则视其与栈顶运算符之间优先级的高低
switch(orderBetween(optr.top(), *S)) { /* 分别处理 */ }
} // while
return opnd.pop(); // 弹出并返回最后的计算结果
}
' 也作为头哨兵首先入栈 while (!optr.empty()) { // 逐个处理各字符,直至运算符栈空 if (isDigit(*S)) // 若当前字符为操作数,则 readNumber(S, opnd); // 读入(可能多位的)操作数 else // 若当前字符为运算符,则视其与栈顶运算符之间优先级的高低 switch(orderBetween(optr.top(), *S)) { /* 分别处理 */ } } // while return opnd.pop(); // 弹出并返回最后的计算结果 }

实现:优先级表

const char pri[N_OPTR][N_OPTR] = { // 运算符优先等级 [栈顶][当前]
  //           |-------------- 当前运算符 --------------|
  //           +    -    *    /    ^    !    (    )    
const char pri[N_OPTR][N_OPTR] = { // 运算符优先等级 [栈顶][当前]
//           |-------------- 当前运算符 --------------|
//           +    -    *    /    ^    !    (    )    \0
/* --  + */ '>', '>', '<', '<', '<', '<', '<', '>', '>',
/*  |  - */ '>', '>', '<', '<', '<', '<', '<', '>', '>',
/* 栈  * */ '>', '>', '>', '>', '<', '<', '<', '>', '>',
/* 顶  / */ '>', '>', '>', '>', '<', '<', '<', '>', '>',
/* 运  ^ */ '>', '>', '>', '>', '>', '<', '<', '>', '>',
/* 算  ! */ '>', '>', '>', '>', '>', '>', ' ', '>', '>',
/* 符  ( */ '<', '<', '<', '<', '<', '<', '<', '=', ' ',
/*  |  ) */ ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ',
/* -- \0 */ '<', '<', '<', '<', '<', '<', '<', ' ', '=',
};
/* -- + */ '>', '>', '<', '<', '<', '<', '<', '>', '>', /* | - */ '>', '>', '<', '<', '<', '<', '<', '>', '>', /* 栈 * */ '>', '>', '>', '>', '<', '<', '<', '>', '>', /* 顶 / */ '>', '>', '>', '>', '<', '<', '<', '>', '>', /* 运 ^ */ '>', '>', '>', '>', '>', '<', '<', '>', '>', /* 算 ! */ '>', '>', '>', '>', '>', '>', ' ', '>', '>', /* 符 ( */ '<', '<', '<', '<', '<', '<', '<', '=', ' ', /* | ) */ ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', /* --
const char pri[N_OPTR][N_OPTR] = { // 运算符优先等级 [栈顶][当前]
//           |-------------- 当前运算符 --------------|
//           +    -    *    /    ^    !    (    )    \0
/* --  + */ '>', '>', '<', '<', '<', '<', '<', '>', '>',
/*  |  - */ '>', '>', '<', '<', '<', '<', '<', '>', '>',
/* 栈  * */ '>', '>', '>', '>', '<', '<', '<', '>', '>',
/* 顶  / */ '>', '>', '>', '>', '<', '<', '<', '>', '>',
/* 运  ^ */ '>', '>', '>', '>', '>', '<', '<', '>', '>',
/* 算  ! */ '>', '>', '>', '>', '>', '>', ' ', '>', '>',
/* 符  ( */ '<', '<', '<', '<', '<', '<', '<', '=', ' ',
/*  |  ) */ ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ',
/* -- \0 */ '<', '<', '<', '<', '<', '<', '<', ' ', '=',
};
*/ '<', '<', '<', '<', '<', '<', '<', ' ', '=', };

实现:不同优先级处理方法

switch(orderBetween(optr.top(), *S) {
    case '<': // 栈顶运算符优先级更低
        optr.push(*S); S++; break;            // 计算推迟,当前运算符进栈
    case '=': // 优先级相等(当前运算符为右括号,或尾部哨兵'
switch(orderBetween(optr.top(), *S) {
case '<': // 栈顶运算符优先级更低
optr.push(*S); S++; break;            // 计算推迟,当前运算符进栈
case '=': // 优先级相等(当前运算符为右括号,或尾部哨兵'\0')
optr.pop(); S++; break;               // 脱括号并接收下一个字符
case '>': // 栈顶运算符优先级更高,实施相应的计算,结果入栈
char op = optr.pop();                 // 栈顶运算符进栈,执行对应的运算
if ('!' == op)
opnd.push(calcu(op, opnd.pop()));               // 一元运算符
else {
float pOpnd2 = opnd.pop(), pOpnd1 = opnd.pop(); // 二元运算符
opnd.push(calcu(pOpnd1, op, pOpnd2));           // 实施计算,结果入栈
}
break;
}
') optr.pop(); S++; break; // 脱括号并接收下一个字符 case '>': // 栈顶运算符优先级更高,实施相应的计算,结果入栈 char op = optr.pop(); // 栈顶运算符进栈,执行对应的运算 if ('!' == op) opnd.push(calcu(op, opnd.pop())); // 一元运算符 else { float pOpnd2 = opnd.pop(), pOpnd1 = opnd.pop(); // 二元运算符 opnd.push(calcu(pOpnd1, op, pOpnd2)); // 实施计算,结果入栈 } break; }

实例

C++ 数据结构(四)栈与队列(2)栈应用(3)中缀表达式

下一篇:《C++ 数据结构(四)栈与队列(2)栈应用(4)逆波兰表达式》

Responses