黑马程序员技术交流社区

标题: 来个题，数据结构的。。。。who can help me [打印本页]

---

作者: 付建超    时间: 2013-9-14 16:14
标题: 来个题，数据结构的。。。。who can help me


做一个表达式的：
在命令行输入：（3+2）*5-5
输出：20


不是要带界面的计算器，用到数据结构的堆栈。。。。。大家伙儿能给解决一下么

---

作者: 471686505    时间: 2013-9-14 17:40
{:soso_e144:}！！！！！！！！！！！！！！1

---

作者: Michael_xpd    时间: 2013-9-14 23:38
要实现这个表达式的求解，可以用算符优先算法。
     定义两个工作栈，一个称作OPTR，用以寄存运算符；另一个称作OPND，用以寄存操作数或运算结果。
算法的基本思想是：
1. 首先置操作数为空栈，表达式起始符“#”为运算符栈的栈底元素；
2. 依次读入表达式中每个字符，若是操作数则进OPND栈，若是运算符则和OPRT栈的栈顶运算符比较优先权后作相应操作，直至整个表达式求值完毕（即OPTR栈的栈 顶元素和当前读入的字符均为“#”）。
算法的代码实现：
OpreandType EvaluateExperession｛
//算术表达式求值的算符优先算法。设OPTR和OPND分别为运算符栈和算术栈，OP为运算符集合。
  InitStack(OPTR); push(OPTR,'#');
   InitStack(OPND); c=getchar();
   while(c!='#'||GetTop(OPTR)!='#'){
       if(!In(c,OP)){Push((OPND,c);c=getchar();}          //不是运算符则进栈
     else
             switch(Precede(GetTop(OPTR),c)){
                 case'<':            //栈顶元素优先权低
                Push(OPTR,c);c=getchar();
                        break;
                case'=':            //脱括号并接收下一字符
                 Pop(OPTR,x);c=getchar();
                         break;
                case'>':           //退栈并将运算结果入栈
                 Pop(OPTR,theta);
                         Pop(OPND,b);      Pop(OPND,a);
                         Push(OPND,Operate(a,theta,b);
                         break;
                }//switch
   }//while
   return GetTop(OPND);
}//EvaluateExpression      

｝

---

欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2