woaidongmao

文章均收录自他人博客,但不喜标题前加-[转贴],因其丑陋,见谅!~
随笔 - 1469, 文章 - 0, 评论 - 661, 引用 - 0
数据加载中……

栈的应用-表达式求值(后缀式)

·       以下就分"如何按后缀式进行运算""如何将原表达式转换成后缀式"两个问题进行讨论。

n       如何按后缀式进行运算?

可以用两句话来归纳它的求值规则:"先找运算符,后找操作数。

   运算过程为:对后缀式从左向右"扫描",遇见操作数则暂时保存,遇见运算符即可进行运算;此时参加运算的两个操作数应该是在它之前刚刚碰到的两个操作数,并且先出现的是第一操作数,后出现的是第二操作数。

n       如何由原表达式转换成后缀式?
先分析一下
原表达式后缀式两者中运算符出现的次序有什么不同。
例一
.  原表达式:a×b/c×d e+f

          后缀式:a b × c / d × e f +

   例二.  原表达式:a+b×c – d/e×f

          后缀式: a b c × + d e / f ×

对原表达式中出现的每一个运算符是否即刻进行运算取决于在它后面出现的运算符,如果它的优先数"高或等于"后面的运算,则它的运算先进行,否则就得等待在它之后出现的所有优先数高于它的"运算"都完成之后再进行。

从原表达式求得后缀式的规则为:
       1) 设立运算符栈;
       2) 设表达式的结束符为“#”,预设运算符栈的栈底为“#”
       3) 若当前字符是操作数,则直接发送给后缀式;
       4) 若当前字符为运算符且优先数大于栈顶运算符,则进栈,否则退出栈顶运算符发送给后缀式;
       5) 若当前字符是结束符,则自栈顶至栈底依次将栈中所有运算符发送给后缀式;
       6) (”对它之前后的运算符起隔离作用,则若当前运算符为“(”时进栈;
       7) ")"可视为自相应左括弧开始的表达式的结束符,则从栈顶起,依次退出栈顶运算符发送给后缀式直至栈顶字符为"("止。

 

void transform(char suffix[ ], char exp[ ] ) {

// 从合法的表达式字符串 exp 求得其相应的后缀式 suffix
InitStack(S); Push(S,
# );
p = exp; ch = *p;
while (!StackEmpty(S)) {

  if (!IN(ch, OP)) Pass( suffix, ch);
  else {
   switch (ch) {
   case ( : Push(S, ch); break;
   case ) : {
             Pop(S, c);
            while (c!= ( )
             { Pass( suffix, c); Pop(S, c);}
                break; }
   default : {

                    while(Gettop(S, c) && ( precede(c,ch)))
               { Pass( suffix, c); Pop(S, c); }
               if ( ch!= # ) Push( S, ch);
               break;
              } // defult
   } // switch
 } // else
 if ( ch!= # ) { p++; ch = *p; }
} // while

} // transform

 

posted on 2010-03-05 16:19 肥仔 阅读(2591) 评论(1)  编辑 收藏 引用 所属分类: 状态机 & 自动机 & 形式语言

评论

# re: 栈的应用-表达式求值(后缀式)  回复  更多评论   

复杂的parser写多了,自然会重新发明boost::spirit车轮一次的,然后从此再也不写parser……
2010-03-06 21:28 | 陈梓瀚(vczh)

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理