逆波兰式也叫后缀表达式(将运算符写在操作数之后)，如：我们平时写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语言的逆波兰式转换，可以参考
阅读(5362) | 评论(1) | 转发(0) |
