逆波兰式也叫后缀表达式(将运算符写在操作数之后),如:我们平时写a+b,这是中缀表达式,写成后缀表达式就是:ab+,使用逆波兰式的好处是有利于计算机运算。当计算机遍历一个逆波兰式时,从式中取出数字压栈,当遇到一个运算符,就将栈顶的两个数进行运算,然后将运算结果压栈,再继续遍历逆波兰式后面的元素。这样,计算机就不需要考虑中坠表达式中的括号、运算顺序等,从而有利于计算机运算。人工将普通表达式转换为逆波兰式时,方法例如: (a+b)*c-(a+b)/e的后缀表达式为:
(a+b)*c-(a+b)/e
→((a+b)*c)((a+b)/e)-
→((a+b)c*)((a+b)e/)-
→(ab+c*)(ab+e/)-
→ab+c*ab+e/-
在计算机中,将一个普通中缀表达式(包含数字,+-*/,括号,函数exp(),log(),pow(,),sin()等)转换为逆波兰式的算法为:
//假设已有一个ArrayList链表a1中包含了一个中缀表达式,要将转换后的逆波兰式放入另一个ArrayList链表a2。
stack fs; //定义一个栈fs
for(int i=0;i
//遍历整个a1,对其中元素依次做相应操作
{
object e = a1[i];
if(e.Type == 数字)////////////////////////////////////////////////////////////
a2.add(e);
else if(e.Type == 左括号或函数)////////////////////////////////////////////////
fs.push(e);
else if(e.Type == +-*/)//////////////////////////////////////////////////////
{
while(fs.count > 0)
{
int tem = compare(e.优先级, fs.peek()) //比较e所代表的符合的优先级与栈顶符号的优先级
if(tem > 0) //如果e的优先级高,则跳出循环,将e压入栈顶
break;
else if(tem == 0) //如果e和栈顶的优先级一样,则将栈顶元素放入a2,然后跳出循环,再将e压入栈顶
{a2.add(fs.pop());break;}
else //如果e的优先级低,则将栈顶元素放入a2,但并不跳出循环,而是重新比较e和下一个栈顶元素的优先级,重复此过程,直到e比栈中所有元素的优先级都高,或栈为空。
a2.add(fs.pop());
}
fs.push(e); //完成上述循环后,将e压入栈,栈内元素情况为:越往顶部,元素优先级越高
}
else if(e.Type == 右括号)///////////////////////////////////////////////////////
{//如果是右括号,则需要将栈顶元素出栈,依次放入a2,直到栈顶元素是左括号或函数
bool tem = false; //先定义一个bool变量,用来表示是否找到了左括号或函数,找到了就不需要向栈的下一个元素比较了
while (fs.Count > 0)
{
object e2 = fs.pop();
if(e2.Type == 左括号或函数)//左括号与函数的差别在于左括号直接舍弃,而函数需要放入a2
{
if(e2.Type == 左括号)
;
else
a2.add(e2);
tem = true;//找到了左括号或函数,则将tem设为true并跳出循环
break;
}
else //如果元素不是左括号或函数,则将此元素放入a2,继续判断下一个栈顶元素
a2.add(e2);
}
if(!tem)//如果循环完了都没有找到左括号或函数,说明原来的表达式有误,左右括号不对称
return false;
}
else if(e.Type == 逗号)//二元函数中的逗号////////////////////////////////////////
{//如果是逗号,则需要将栈顶元素出栈,依次放入a2,直到栈顶元素是二元函数
bool tem = false; //先定义一个bool变量,用来表示是否找到了左括号或函数,找到了就不需要向栈的下一个元素比较了
while (fs.Count > 0)
{
object e2 = fs.peek();
if(e2.Type == 二元函数)//左括号与函数的差别在于左括号直接舍弃,而函数需要放入a2
{
tem = true;//找到了二元函数,则将tem设为true并跳出循环
break;
}
else //如果元素不是二元函数,则将此元素放入a2,继续判断下一个栈顶元素
a2.add(e2);
}
if(!tem)//如果循环完了都没有找到二元函数,说明原来的表达式有误,不应该出现逗号
return false;
}
else
//////////////////////////////////////////////////////////////////////////
;//e.Type除了等于以上几种类型外,也不可能等于其他类型了,else只是作为语句与if对应
}
while (fs.Count > 0) //遍历完a1后,将栈中剩余的元素依次放入a2
a2.add(fs.pop());
//最后a2中元素的顺序就是逆波兰式了。
关于C语言的逆波兰式转换,可以参考
阅读(5388) | 评论(1) | 转发(0) |