黑马程序员技术交流社区

标题: 如何将中缀的字符串形式算数表达式转成后缀的 [打印本页]
作者: ppStudent    时间: 2014-12-1 09:58
标题: 如何将中缀的字符串形式算数表达式转成后缀的
  1. public static ArrayList<String> toBehind(ArrayList<String> al)
  2.         {
  3.                 ArrayList<String> ak = new ArrayList<String>();
  4.                 Stack<String> s=new Stack<String>();
  5.                 for(int i=0;i<al.size();i++)
  6.                 {
  7.                         if(Character.isDigit(al.get(i).charAt(0)))//某位元素的第一个字符是否为数字
  8.                                 ak.add(al.get(i));
  9.                         else
  10.                         {   
  11.                                 while(!s.isEmpty()&&compared(s.peek(),al.get(i)))//栈内部没有泛型的话都是存储的object对象。
  12.                                 {
  13.                                         ak.add(s.pop());
  14.                                 }
  15.                                 s.push(al.get(i));
  16.                         }
  17.                 }
  18.                 System.out.println("转换成后缀表达式为：");
  19.                 for(String ss:ak)
  20.                 {
  21.                         System.out.print(ss+" ");
  22.                 }
  23.                 System.out.println();
  24.                 return ak;//返回的后缀表达式没有"#"了
  25.         }
复制代码

比如“3+4/5”这样一个字符串，我现在要将这个字符串的每一个字符都变得有意义，然后我可以计算这个算术？如何将这个表达式转换成后缀表达式呢？
由中缀表达式转化为后缀表达的具体步骤：
① 在表达式字符串的末尾加一个代表结束的辅助符,比如”#”。
② 从头开始扫描表达式，并判断当前的每一个字符。
③ 取当前的一个字符，如果当前字符是代表数字，则存入集合中，如果是运算符，则转入④，如果是“#“，则结束。
④ 比较当前运算符与临时栈中的栈顶运算符，如果栈顶运算符比当前运算符优先级高，则弹出一个运算符放进集合中，并继续④
否则把当前运算符进栈，转入②.
作者: kerner    时间: 2014-12-1 10:51
不错，顶一个，栈合理应用的地方。



欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/) 黑马程序员IT技术论坛 X3.2