上一篇
下一篇
编译原理-中缀表达式转后缀表达式(逆波兰式)
作者:dh20156 日期:2009-12-03
中缀表达式转后缀表达式(逆波兰式)算法，后缀表达式求值算法
3 + 4 * 5 - 6;
OS DS
3
+ 3
+ 34
*+ 34
*+ 345
+ 345*
- 345*+
- 345*+6
345*+6-
插入运算符 o 时，
如果优先级 o>OS[0]，
则：遇到')'时，o2 = OS.shift(),DS.push(o2),DS.shift()，否则OS.unshift(o)；
否则o2 = OS.shift(),DS.push(o2),OS.unshift(o)，连续判断，直到OS[0]优先级>o；
例
3 + 4 / ( 25 - ( 6 * 5 ) ) * 8 #
1
3 + 4 / ( 25 - ( 6 * 5 ) ) * 8 #
↑
OS DS
3
2
3 + 4 / ( 25 - ( 6 * 5 ) ) * 8 #
↑
OS DS
+ 3
3
3 + 4 / ( 25 - ( 6 * 5 ) ) * 8 #
↑
OS DS
+ 3 4
4
3 + 4 / ( 25 - ( 6 * 5 ) ) * 8 #
↑
OS DS
/
+ 3 4
5
3 + 4 / ( 25 - ( 6 * 5 ) ) * 8 #
↑
OS DS
(
/
+ 3 4
6
3 + 4 / ( 25 - ( 6 * 5 ) ) * 8 #
↑
OS DS
(
/
+ 3 4 25
7
3 + 4 / ( 25 - ( 6 * 5 ) ) * 8 #
↑
OS DS
－
(
/
+ 3 4 25
8
3 + 4 / ( 25 - ( 6 * 5 ) ) * 8 #
↑
OS DS
(
－
(
/
+ 3 4 25
9
3 + 4 / ( 25 - ( 6 * 5 ) ) * 8 #
↑
OS DS
(
－
(
/
+ 3 4 25 6
10
3 + 4 / ( 25 - ( 6 * 5 ) ) * 8 #
↑
OS DS
*
(
－
(
/
+ 3 4 25 6
11
3 + 4 / ( 25 - ( 6 * 5 ) ) * 8 #
↑
OS DS
*
(
－
(
/
+ 3 4 25 6 5
12
3 + 4 / ( 25 - ( 6 * 5 ) ) * 8 #
↑
OS DS
－
(
/
+ 3 4 25 6 5 *
12
3 + 4 / ( 25 - ( 6 * 5 ) ) * 8 #
↑
OS DS
/
+ 3 4 25 6 5 * -
13
3 + 4 / ( 25 - ( 6 * 5 ) ) * 8 #
↑
OS DS
*
+ 3 4 25 6 5 * - /
14
3 + 4 / ( 25 - ( 6 * 5 ) ) * 8 #
↑
OS DS
*
+ 3 4 25 6 5 * - / 8
15
3 + 4 / ( 25 - ( 6 * 5 ) ) * 8 #
↑
OS DS
3 4 25 6 5 * - / 8 * +
<script type="text/javascript">
//中缀表达式转后缀表达式
var ie2se = function(mExp){
var exp2array = function(exp){
var ret = [];
exp.replace(/([^\d])|(\d*)/g,function(s,a,b){if(a){ret.push(a);}if(b){ret.push(b)}});
return ret.slice(0);
};
//将中缀表达式打散为数组形式
var remExp = exp2array(mExp);
//运算符栈和数据栈
var OS = [],DS = [];
//换算运算符优先级
var r = /(?:([+-])|([*\/])|([\(\)]))/;
var getPRI = function(o){
r.test(o);
return RegExp.$2?1:RegExp.$3?2:0;
};
var tmpItem = null,OSTop = null,pti = 0,ptt = 0;
while(remExp.length){
//取剩余表达式中第一个元素
tmpItem = remExp.shift();
OSTop = OS[0];
if(isNaN(tmpItem)){//运算符
pti = getPRI(tmpItem);
ptt = getPRI(OSTop);
if(pti>ptt){//优先级高于OS[0]
if(tmpItem!=')'){//运算符不是右括号
OS.unshift(tmpItem);
}else{
DS.push(OS.shift());
OS.shift();//丢掉'(';
}
}else{//优先级低于或等于OS[0]
//循环判断，直至OS[0]优先级大于当前运算符
while(OS.length&&OS[0]!='('&&pti<=getPRI(OS[0])){
DS.push(OS.shift());
}
OS.unshift(tmpItem);
}
}else{//数据
DS.push(tmpItem);
}
}
//剩余表达式为空后，将OS栈的元素都push到DS栈
while(OS.length){DS.push(OS.shift());}
return DS.slice(0);
};
//后缀表达式求值
var suffix_compute = function(suffixExp){
var ret = suffixExp.slice(0);
while(ret.length>1){
var idx = 0;//第一个运算符出现的位置
for(var i=0;i<ret.length;i++){if(isNaN(ret[i])){idx = i-2;break;}}
//取出该位置前及其前两个元素
var a = ret.splice(idx,1);
var b = ret.splice(idx,1);
var o = ret.splice(idx,1);
//计算
var e = eval('('+a+')'+o+'('+b+')');
//计算结果插入到该位置
ret.splice(idx,0,e);
}
return ret[0];
};
var me = '3+4/(25-(6*5))*8';
var se = ie2se(me);
var d = suffix_compute(se);
document.write('<h3>中缀表达式转后缀表达式计算结果：</h3>'+me+' = '+eval(me)+'<br/>'+se+' = '+d);
</script>
[本日志由 dh20156 于 2009-12-05 05:57 PM 编辑]
文章来自: DHTML精英,WEB前端专家!
引用通告: 查看所有引用 | 我要引用此文章
Tags: 编译原理 中缀表达式 后缀表达式 逆波兰式
文章来自: DHTML精英,WEB前端专家!引用通告: 查看所有引用 | 我要引用此文章Tags: 编译原理 中缀表达式 后缀表达式 逆波兰式 评论: 0 | 引用: 0 | 查看次数: 1830
发表评论
