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

《【题01】计算表达式值--试题解析》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、【题1】计算表达式值输入一个表达式，该表达式含‘+’、‘-’、‘*’、‘/’和操作数，所含字符数不超过255，以‘@’结束。输出该表达式的值。分析：由于一个表达式含操作数、运算符和括号，因此只能采用字符串类型输入，而字符是不能进行数值计算的。在这种情况下，计算机又如何计算表达式的值呢。一般方法是中缀表达式→等价的后缀表达式→计算后缀表达式的值1、中缀表达式和后缀表达式的特征中缀表达式：中缀表达式与通常的表达式一样，运算符位于两个操作之间，计算规则为①先括号内、后括号外；②无括号或同层括号内先*、/、后+、-；③同级运算按由左至右顺序进行。为了计算方便，输入的中缀表达式串以‘@’

2、为结束标志。例如3*(5–2)+7@后缀表达式：后缀表达式中不再引入括号，运算符放在两个运算对象之后。所有计算按运算符出现的顺序，严格地由左而右进行（不再考虑运算符的优先规则）。为了计算方便，以‘.’为操作数的结束标志，以‘@’为后缀表达式的结束标志。例如3*（5-2）+7@对应的后缀表达式为3．5．2．-*7．+。后缀表达式是简化运算顺序的一种表达式。2、将中缀表达式转换为等价的后缀表达式在中缀表达式中，运算符出现次序与计算顺序不一致，实际计算顺序不仅要看它的出现次序，还要受运算符的优先级和括号的影响。如果把一个中缀表达式中所有的计算顺序都按计算规则用嵌套括号的形式表示出来，

3、其转换过程就要清楚的多。例如中缀表达式3*(5–2)+7@可以改写成（(3*(5–2))+7）@。这时可以看出，只要将每对括号中的运算符移到相应括号的后面，再删去所有括号，便得到与之等价的后缀表达式3．5．2．*7．+@。为了将中缀表达式转换为等价的后缀表达式，需要从左至右扫描中缀表达式，并使用一个栈s2来存放中缀表达式中的开括号‘（’和暂时不能参与计算的运算符，显然s2栈的元素类型为char。为了方便表达式值的计算，在转换后的后缀表达式中，每一个操作数尾添加一个‘.’。例如计算3*(5–2)+7@具体算法如下：vara，e：string；{后缀表达式和中缀表达式}s2：arr

4、ay[1..100]ofchar；{栈，存放暂不参与计算的运算符}t，i：integer；{栈顶指针、中缀表达式的字符指针}w：char；begin读中缀表达式e；a←‘’；{后缀表达式初始化为空}i←1；t←0；{从中缀表达式的第一个字符开始分析，栈空}whilee[i]<>’@’do{由左而右扫描处理中缀表达式的每一个字符}４begincasee[i]of‘0’‥’9’：begin{操作数进入后缀表达式}whilee[i]in[0..9]dobegina←a+e[i]；i←i+1；end；{while}a←a+’．’；i←i-1；{添加操作数的结尾标志}end；{‘0’‥’

5、9’}‘(’：push(s2．’（’，t)；{‘（’入栈}‘)’：begin{s2栈中栈顶至’(’间的所有运算符相继出栈，进入后缀表达式}w←pop(s2，t)；whilew<>’(’dobegina←a+w；w←pop(s2，t)；end；{while}end；{‘）’}‘+’，’-’：begin{s2栈中，栈顶至’(’前的所有运算符相继出栈，进入后缀表达式，e[i]进入s2栈}ift<>0thenbeginw←top(s2，t)；whilew<>’(’dobegina←a+w；w←pop(s2，t)；ift=0thenbreakelsew←top(s2，t)；end；{wh

6、ile}end；{then}push(s2，e[i]，t)；end；{‘+’，’-’}‘*’，’/’：begin{s2栈中栈顶至第1个’+’或’-’前的所有运算符相继出栈，进入后缀表达式，e[i]进入s2栈}ift<>0thenbeginw←top(s2，t)；while(w=’*’)or(w=’/’)dobegina←a+w；w←pop(s2，t)；ift=0thenbreakelsew←top(s2，t)；end；{while}end；{then}push(s2，e[i]，t)；end；{‘*’，’/’}end；{case}i←i+1；{准备扫描处理中缀表达式的下一个字符}

7、end；{while}whilet<>0do{s2栈中的运算符相继出栈，进入后缀表达式}begina←a+pop(s2，t)；４end；{while}a←a+’@’；输出后缀表达式a；end；{算法结束}3、计算后缀表达式的值有了后缀表达式，便可以按照由左而右的顺序计算表达式的值。3．5．2．-*7．+@=3．3．*7．+@=9．7．+@=16这个计算结果正好为表达式3*(5–2)+7的值。在计算过程中，我们使用栈s存放操作数和计算结果，显然s的元素类型为整型。计算过程如下：由左而右处理后缀