学步园

public class NiBoLan {
 private static final int MAX_NODE = 100;

 // 二叉树的结点类
 private static class MyTreeNode {
  public double value;// 若结点是数字，则保存为该结点的值；若是符号，则此字段无意义
  public char symbol;// '+','-','*','/','d'
  public int left;// 左孩子
  public int right;// 右孩子
  public int father;// 爹地

  public void init() {
   value = 0;
   symbol = '\0';
   left = -1;
   right = -1;
   father = -1;
  }
 }

 private static boolean isOperator(char c) {
  if (c == '+' || c == '-' || c == '*' || c == '/') {
   return true;
  }
  return false;
 }

 private static boolean isDigit(char c) {
  if ((c <= '9' && c >= '0') || c == '.') {
   return true;
  }
  return false;
 }

 // 用递归计算树的值
 private static double getNodeValue(MyTreeNode[] tree, int nodeNum)
   throws Exception {
  // 如果结点是数字，直接返回值
  if (tree[nodeNum].symbol == 'd') {
   return tree[nodeNum].value;
  }
  // 如果结点是符号，则递归计算
  if (tree[nodeNum].symbol == '+') {
   return getNodeValue(tree, tree[nodeNum].left)
     + getNodeValue(tree, tree[nodeNum].right);
  }
  if (tree[nodeNum].symbol == '-') {
   return getNodeValue(tree, tree[nodeNum].left)
     - getNodeValue(tree, tree[nodeNum].right);
  }
  if (tree[nodeNum].symbol == '*') {
   return getNodeValue(tree, tree[nodeNum].left)
     * getNodeValue(tree, tree[nodeNum].right);
  }
  if (tree[nodeNum].symbol == '/') {
   return getNodeValue(tree, tree[nodeNum].left)
     / getNodeValue(tree, tree[nodeNum].right);
  }
  throw new Exception("tree error");
 }

 // 计算逆波兰表达式
 public static double calculate(String str) {
  double result = 0;
  MyTreeNode tree[] = new MyTreeNode[MAX_NODE];
  for (int i = 0; i < MAX_NODE; i++) {
   tree[i] = new MyTreeNode();
   tree[i].init();
  }
  int nowCount = 0;
  int pointerTmp = -1;

  try {
   // 建立整棵二叉树
   // 注意，逆波兰式解析起来应该是从右向左
   for (int i = str.length() - 1; i >= 0; i--) {
    if (isOperator(str.charAt(i)) || isDigit(str.charAt(i))) {
     // 若是符号
     if (isOperator(str.charAt(i))) {
      tree[nowCount].symbol = str.charAt(i);
     }
     // 若是数字
     else if (isDigit(str.charAt(i))) {
      int numEnd = i;
      while (isDigit(str.charAt(i))) {
       i--;
       if (i < 0) {
        break;
       }
      }
      i++;
      tree[nowCount].value = Double.valueOf(str.substring(i,
        numEnd + 1));
      tree[nowCount].symbol = 'd';
     }

     // 现在开始的代码为核心+关键
     // 向上找到父结点，挂载当前结点，构建二叉树
     pointerTmp = nowCount - 1;
     while (pointerTmp >= 0) {
      // 因为数字一定在叶子结点上，因此忽略数字结点
      // 优先查看找到的非叶子的右孩子，如果为空，就认其为父
      if (tree[pointerTmp].right < 0
        && tree[pointerTmp].symbol != 'd') {
       tree[pointerTmp].right = nowCount;
       tree[nowCount].father = pointerTmp;
       break;
      }
      // 如果右孩子非空，就看左孩子，如果为空，就认贼作父
      if (tree[pointerTmp].left < 0
        && tree[pointerTmp].symbol != 'd') {
       tree[pointerTmp].left = nowCount;
       tree[nowCount].father = pointerTmp;
       break;
      }
      // 如果都不为空，继续向上查找。"我要我要找我爸爸，去到哪里也要找我爸爸~~~"
      pointerTmp = tree[pointerTmp].father;
     }
     // 如果找不到爹地，哼哼，那怎么可能！难道是无性繁殖？
     if (nowCount != 0 && pointerTmp < 0) {
      throw new Exception("我靠，你就不能写个正确的表达式阿");
     }
     nowCount++;
    }
   }
   // 计算结果
   result = getNodeValue(tree, 0);
  } catch (Exception e) {
   // 如果表达式错误，输出提示
   System.out.println("The next expression error!");
   result = 0;
  }

  return result;
 }

 public static void main(String[] args) {

  String str = "1 2 3 4 5*-6 + -*";
  String str2 = "1.23 252.6 3 4.8 5* - * 6 + *";
  String str3 = "1.23 252.6 3 4.8 5* - * 6 ++ *";// 这个表达式是错的，输出错误提示
  String str4 = "1.23 252.6 3 4.8 5";// 这个表达式还是错的，输出错误提示
  System.out.println(str + " = " + calculate(str));
  System.out.println(str2 + " = " + calculate(str2));
  System.out.println(str3 + " = " + calculate(str3));
  System.out.println(str4 + " = " + calculate(str4));
 }
}