济南大学信息科学与工程学院数据结构课件 第三章.ppt

关于中缀表达式与后缀表达式转换 第一步：将中缀表达式所有的子表达式按计算规则用嵌套括号括起来； 第二步：顺序将每对括号中的运算符移到相应括号后面； 第三步：删除所有括号。 例： a+b*( c-d )–e/f 中缀表达式 第一步： ((a+(b*( c-d )))–(e/f )) 第二步： ((a(b( c d )-)*) +(e f )/) – 第三步： abcd - * + e f / – 后缀表达式 5. 栈的应用——表达式计算 应用后缀表示计算表达式的值 从左向右顺序地扫描表达式，并用一个栈 暂存扫描到的操作数或计算结果。 在后缀表达式的计算顺序中已隐含了加括号 的优先次序，括号在后缀表达式中不出现。 计算例 A B C D - * + E F / - R1 R2 R3 R4 R5 4 ＋ 2 * 3 － 10 / 5 # (中缀表达式） OPND OPTR 当前输入符c # 4 4 + # + + 2 2 * + * * 3 3 - * - 6 + - 10 # - - 10 10 / - / / 5 5 # / # 2 - # 8 # = # return 8 初始，# 进OPTR栈 4 2 3 * + 10 5 / - (后缀表达式） OPND 当前输入符c 4 2 return 8 4 2 3 3 * 2*3 6 + 4+6 10 10 5 10 5 / 10/5 2 - 10-2 8 5. 栈的应用——表达式计算 模拟一个简单的计数器 class Calculator //计数器类的定义 { public: Calculator(int sz):s(sz){} void Run(); private: SeqStackdouble s; bool Get2Operands( double left, double right); void DoOperator(char op); }; 模拟一个简单的计数器 void Calculator::Run() { char ch; double newOperand; while(cinch, ch!=#) { switch(ch) { case +: case -: case *: case /: DoOperator(ch); break; default: cin.putback(ch); cinnewOperand; s.Push(newOperand); } } s.output(); s.MakeEmpty(); } 模拟一个简单的计数器 void Calculator::DoOperator(char op) { double left, right, value; bool result; result=Get2Operands(left,right); if(result== true) switch(op) { case +: value=left+right; s.Push(value); break; case -: value=left-right; s.Push(value); break; case *: value=left*right; s.Push(value); break; case /: if(fabs(right)0.0001) { cout除数为0!\n; s.MakeEmpty(); } else { value=left/right; s.Push(value); } break; } else s.MakeEmpty(); } 模拟一个简单的计数器 bool Calculator::Get2Operands(double left,