计算表达式值试题解析.docxVIP

【题1】计算表达式值

输入一个表达式，该表达式含‘+’、‘-’、‘*’、‘/’和操作数，所含字符数不超过255，以‘@’结束。输出该表达式的值。

分析：

由于一个表达式含操作数、运算符和括号，因此只能采用字符串类型输入，而字符是不能进行数值计算的。在这种情况下，计算机又如何计算表达式的值呢。一般方法是

中缀表达式→等价的后缀表达式→计算后缀表达式的值

1、中缀表达式和后缀表达式的特征

中缀表达式：中缀表达式与通常的表达式一样，运算符位于两个操作之间，计算规则为

①先括号内、后括号外；

②无括号或同层括号内先*、/、后+、-；

③同级运算按由左至右顺序进行。

为了计算方便，输入的中缀表达式串以‘@’为结束标志。例如3*(5–2)+7@

后缀表达式：后缀表达式中不再引入括号，运算符放在两个运算对象之后。所有计算按运算符出现的顺序，严格地由左而右进行（不再考虑运算符的优先规则）。为了计算方便，以‘.’为操作数的结束标志，以‘@’为后缀表达式的结束标志。例如 3*（5-2）+7@ 对应的后缀表达式为3．5．2．-*7．+。后缀表达式是简化运算顺序的一种表达式。

2、将中缀表达式转换为等价的后缀表达式

在中缀表达式中，运算符出现次序与计算顺序不一致，实际计算顺序不仅要看它的出现次序，还要受运算符的优先级和括号的影响。如果把一个中缀表达式中所有的计算顺序都按计算规则用嵌套括号的形式表示出来，其转换过程就要清楚的多。例如中缀表达式3*(5–2)+7@可以改写成

（(3*(5–2))+7）@。这时可以看出，只要将每对括号中的运算符移到相应括号的后面，再删去所有括号，便得到与之等价的后缀表达式3．5．2．*7．+@。

为了将中缀表达式转换为等价的后缀表达式，需要从左至右扫描中缀表达式，并使用一个栈s

2

来存放中缀表达式中的开括号‘（’和暂时不能参与计算的运算符，显然s

2

栈的元素类型为char。

为了方便表达式值的计算，在转换后的后缀表达式中，每一个操作数尾添加一个‘ .’。例如计算

3*(5–2)+7@

具体算法如下：

var

a，e：string； {后缀表达式和中缀表达式}

s：array[1..100]ofchar； {栈，存放暂不参与计算的运算符}

2

t，i：integer； {栈顶指针、中缀表达式的字符指针}

w：char；begin

读中缀表达式e；

a←‘’； {后缀表达式初始化为空}

i←1；t←0； {从中缀表达式的第一个字符开始分析，栈空}

whilee[i]’@’do {由左而右扫描处理中缀表达式的每一个字符}

１

begin

casee[i]of

‘0’‥’9’：begin {操作数进入后缀表达式}

whilee[i]in[0..9]dobegin

a←a+e[i]；i←i+1；end；{while}

a←a+’．’；i←i-1； {添加操作数的结尾标志}end；{‘0’‥’9’}

‘(’ ：push(s．’（’，t)； {‘（’入栈}

2

‘)’：begin {s

2

栈中栈顶至’(’间的所有运算符相继出栈，进入后缀表达式}

w←pop(s，t)；

2

whilew’(’do

begin

a←a+w；w←pop(s，t)；

2

end；{while}

end；{‘）’}

进入s栈}

2

‘+’，’-’：begin{s

2

ift0

栈中，栈顶至’(’前的所有运算符相继出栈，进入后缀表达式，e[i]

thenbegin

w←top(s，t)；

2

whilew’(’do

begin

a←a+w；w←pop(s，t)；

2

ift=0thenbreak

elsew←top(s，t)；

2

end；{while}

end；{then}

push(s，e[i]，t)；

2

end；{‘+’，’-’}

‘*’，’/’： begin{s

2

栈中栈顶至第1个’+’或’-’前的所有运算符相继出栈，进入后缀表

达式，e[i]进入s栈}

2

ift0thenbegin

w←top(s，t)；

2

while(w=’*’)or(w=’/’)do

begin

a←a+w；w←pop(s，t)；

2

ift=0thenbreak

elsew←top(s，t)；

2

end；{while}

end；{then}push(s，e[i]，t)；

2

end；{‘*’，’/’}

end；{case}

i←i+1； {准备扫描处理中缀表达式的下一个字符}end；{while}

whilet0do {s栈中的运算符相继出栈，进入后缀表达式}

2

begin

a←a+pop