首先谈谈统一进程:
1 .从左到右依次读取公式中的一个字符
2 .读完括号后,跳过进入下一个字符
3 .读取的字符为数字时,直接输出到结果字符串的末尾。 结果字符串是所需的后缀表达式,直到结束。
4 .如果读了运算符,则将运算符放入堆栈
(1)堆栈空闲时,直接进入堆栈;
)2)如果堆栈不空,则判断堆栈顶部运算符的优先级:
1如果堆栈顶部运算符的优先级低于堆栈运算符,则直接堆栈
2如果堆栈顶部运算符的优先级高于进入堆栈的运算符,则将堆栈顶部位置的优先级高的运算符输出到堆栈,并将堆栈的运算符输出到结果字符串的末尾,直到堆栈顶部运算符的优先级低于进入堆栈的运算符。 (实际上,使堆栈中运算符的优先级从堆栈顶部到堆栈底部按从高到低的顺序依次降低) ) ) )。
5 .按上述顺序读取,直到下一个骑马订公式读取完毕,最后的结果保存在该结果字符串中。
6 .最后堆栈堆栈中还有的运算符,并将其添加到结果字符串中。 得到后缀表达式
例1 * 2说明(2-1)
对等式1*2(2-1)来说,这是http://www.Sina.com/http://www.Sina.com/:
结果字符串String result=' '; //开始为空
将存储运算符的堆栈设为stack=空//开始为空,从左到右为堆栈底和堆栈顶
第一个字符为1,结果字符串result=='1';
第二个字符为*,堆栈为空, stack=*
第三个字符为2,结果字符串result=='12 ';
第四个字符.堆栈不为空,输入.堆栈顶部运算符*的优先级高于输入的运算符,因此*先输出,并添加到结果字符串中
result=='12* '; 然后堆栈=
第5个字符是(直接跳过
第六个字符是2,其中包含结果字符串result=='12*2'
第7个字符是- .堆栈不为空,进入堆栈,堆栈顶部运算符的优先级高于进入堆栈的运算符-,所以先提取堆栈,添加到结果字符串中
result=='12*2'; 然后堆栈=-
第七个字符为1,其中包含结果字符串result=='12*2 1 '
第8个字是) .跳过,
这样,骑马订式的读取就完成了
将堆栈中的运算符按顺序堆栈并添加到结果字符串中
result=='12*2 1-'得到了最终的后缀表达式
第二个问题: 中缀表达式(就是平时计算用的式子)
1 .从左到右依次读取后缀表达式
2 .读完数字后,直接进入堆栈
3 .读完运算符后,从堆栈中提取堆栈顶部的两个数字,并与此运算符进行运算
请注意,之前堆栈的数量是减数,之后堆栈的数量是被减数。 (除法很相似。
将此计算的结果推入堆栈
4 .重复上述步骤,堆栈中存在最终运算结果
例:上得到的后缀表达式:12*2 1-
堆栈为堆栈
第一个字符1,堆栈=1
第二个字符2,堆栈=12
第3个字符* .堆栈元素通过运算1*2得到,重新堆栈stack=2
的4个字符2,堆栈=22
第5个字符,堆栈要素通过运算2 2得到4,再堆栈stack=4
第6个字符1,堆栈=41
第7个字符-,堆栈元素进行运算4-1得到3,重新堆栈stack=3
到此为止,后缀表达式的读取完成,最终结果3被保存在堆栈中
也可以计算为与原来的骑马订式1*2(2-1)相同的结果吧~
https://转载自zhidao.Baidu.com/question/18934571538369780.html