【题01】计算表达式值--试题解析.doc

【题1】计算表达式值 输入一个表达式，该表达式含+、-、*、/和操作数，所含字符数不超过255，以结束。输出该表达式的值。分析：由于一个表达式含操作数、运算符和括号，因此只能采用字符串类型输入，而字符是不能进行数值计算的。在这种情况下，计算机又如何计算表达式的值呢。一般方法是中缀表达式等价的后缀表达式计算后缀表达式的值1、中缀表达式和后缀表达式的特征中缀表达式：中缀表达式与通常的表达式一样，运算符位于两个操作之间，计算规则为先括号内、后括号外；无括号或同层括号内先*、/、后+、-；同级运算按由左至右顺序进行。为了计算方便，输入的中缀表达式串以为结束标志。例如3*(52)+7后缀表达式：后缀表达式中不再引入括号，运算符放在两个运算对象之后。所有计算按运算符出现的顺序，严格地由左而右进行（不再考虑运算符的优先规则）。为了计算方便，以.为操作数的结束标志，以为后缀表达式的结束标志。例如3*（5-2）+7 对应的后缀表达式为 352-*7+。后缀表达式是简化运算顺序的一种表达式。2、将中缀表达式转换为等价的后缀表达式在中缀表达式中，运算符出现次序与计算顺序不一致，实际计算顺序不仅要看它的出现次序，还要受运算符的优先级和括号的影响。如果把一个中缀表达式中所有的计算顺序都按计算规则用嵌套括号的形式表示出来，其转换过程就要清楚的多。例如中缀表达式3*(52)+7可以改写成（(3*(52)+7）。这时可以看出，只要将每对括号中的运算符移到相应括号的后面，再删去所有括号，便得到与之等价的后缀表达式352*7+ 。为了将中缀表达式转换为等价的后缀表达式，需要从左至右扫描中缀表达式，并使用一个栈s2来存放中缀表达式中的开括号（和暂时不能参与计算的运算符，显然s2栈的元素类型为char。为了方便表达式值的计算，在转换后的后缀表达式中，每一个操作数尾添加一个.。例如计算3*(52)+7具体算法如下： var a，e：string； 后缀表达式和中缀表达式 s2：array1.100of char； 栈，存放暂不参与计算的运算符 t，i：integer； 栈顶指针、中缀表达式的字符指针 w：char； begin 读中缀表达式e；a； 后缀表达式初始化为空 i1；t0； 从中缀表达式的第一个字符开始分析，栈空 while ei do 由左而右扫描处理中缀表达式的每一个字符 begin case eiof 09：begin 操作数进入后缀表达式 while ei in0.9 do begin aa+ei； ii+1； end；while aa+；ii-1； 添加操作数的结尾标志 end；09 ( ： push (s2（， t)； （入栈 ) ： begin s2栈中栈顶至(间的所有运算符相继出栈，进入后缀表达式 wpop(s2，t)； while w( do begin aa+w；wpop(s2，t)； end；while end；） +，-： begins2栈中，栈顶至(前的所有运算符相继出栈，进入后缀表达式，ei进入s2栈 if t0 then begin wtop (s2，t)； while w( do begin aa+w；wpop (s2，t)； if t=0 then break else wtop (s2，t)； end；while end；then push (s2，ei，t)； end；+，- *，/： begins2栈中栈顶至第1个+或-前的所有运算符相继出栈，进入后缀表达式，ei进入s2栈 if t0 then begin wtop (s2，t)； while (w=*) or (w=/)do begin aa+w； wpop (s2，t)； if t=0 then break else wtop (s2，t)； end；while end；then push(s2，ei，t)； end；*，/ end；case ii+1； 准备扫描处理中缀表达式的下一个字符 end；while while t0 do s2栈中的运算符相继出栈，进入后缀表达式 begin aa+pop (s2，t)； end；while aa+； 输出后缀表达式a； end； 算法结束3、计算后缀表达式的值有了后缀表达式，便可以按照由左而右的顺序计算表达式的值。 352-*7+ =33*7+ =97+ =16这个计算结果正好为表达式3*(52)+7的值。在计算过程中，我们使用栈s存放操作数和计算结果，显然s的元素类型为整型。计算过程如下：由左而右处理后缀表达式串a中的每一个字符。如遇到一个操作数，就送入s栈中保存；如遇到一个运算符，就从栈中取出栈顶的两个操作数进行计算，然后将计算结果重新压入栈中。依次类推，直至表达式最后一个运算符处理完毕，这时的栈顶元素值即为计算结果。例如计算后缀表达式352-*7+的值具体算法如下： var s： array1.100of longint； 栈 a： string； 后缀表达式 t，i，j，k ：integer； t栈顶指针；i后缀表达式的字符指针；k、j操作数值 begin 输入中缀表达式，计算等价的后缀表达式a； i1； t0； 后缀表达式的字符指针和栈顶指针初始化 while ai do 若后缀表达式末处理完，则循环 begin case ai of 09： begin 取出以ai为首的操作数，存入s栈 k0； repeat k10*k+ord(ai)-ord(0)； ii+1； until ai= ； push (s，k，t)； 操作数k压入s栈 end； 09 +： push(s，pop (s，t)+pop(s，t)，t)；取出栈顶的两个操作数进行加法运算，其和重新压入栈中 -： begin 取出栈顶的两个操作数进行减法运算，其差重新压入栈中 jpop (s，t)； push (s，pop (s，t) j， t)； end； - *： push (s，pop(s，t)*pop(s，t)，t)；取出栈顶的两个操作数进行乘法运算，其积重新压入栈中 /： begin 取出栈顶的两个操作数