`
totty
  • 浏览: 23343 次
  • 性别: Icon_minigender_1
  • 来自: 北京
最近访客 更多访客>>
文章分类
社区版块
存档分类
最新评论

数据结构之中缀表达式转为后缀表达式

数据结构 
阅读更多

将中缀表达式转为后缀表达式后，利用计算机计算表达式更容易。

ExpressionCal.java 代码
  1. public class ExpressionCal {   
  2.   
  3.     // 构建一个栈   
  4.     class Stack {   
  5.   
  6.         private int top;   
  7.   
  8.         private char[] stackArray;   
  9.   
  10.         // 栈构造函数   
  11.         public Stack(int s) {   
  12.             stackArray = new char[s];   
  13.             top = -1;   
  14.         }   
  15.   
  16.         // 入栈   
  17.         public void push(char i) {   
  18.             stackArray[++top] = i;   
  19.         }   
  20.   
  21.         // 出栈   
  22.         public char pop() {   
  23.             return stackArray[top--];   
  24.         }   
  25.   
  26.         public int size() {   
  27.             return top + 1;   
  28.         }   
  29.   
  30.         public boolean isEmpty() {   
  31.             return (top == -1);   
  32.         }   
  33.   
  34.         public void displayStack(String s) {   
  35.             System.out.print(s);   
  36.             for (int i = 0; i < size(); i++) {   
  37.                 System.out.print(stackArray[i]);   
  38.                 System.out.print(' ');   
  39.             }   
  40.             System.out.println(" ");   
  41.         }   
  42.   
  43.     }   
  44.   
  45.     // 将中缀表达式转换为后缀表达式类   
  46.     class PostExpression {   
  47.         private Stack postExpStack;   
  48.   
  49.         private String input;   
  50.   
  51.         private String output = "";   
  52.   
  53.         public PostExpression(String expression) {   
  54.             input = expression;   
  55.             postExpStack = new Stack(expression.length());   
  56.         }   
  57.   
  58.         // 将中缀表达式变成后缀表达式   
  59.         public String transPostExp() {   
  60.             for (int i = 0; i < input.length(); i++) {   
  61.                 postExpStack.displayStack("no" + i + " stack is: ");   
  62.                 char ch = input.charAt(i);   
  63.                 switch (ch) {   
  64.                 case '+':   
  65.                 case '-':   
  66.                     doOper1(ch, 1);   
  67.                     break;   
  68.                 case '*':   
  69.                 case '/':   
  70.                     doOper1(ch, 2);   
  71.                     break;   
  72.                 case '(':   
  73.                     postExpStack.push(ch);   
  74.                     break;   
  75.                 case ')':   
  76.                     doOper2();   
  77.                     break;   
  78.                 default:   
  79.                     output += ch;   
  80.                     break;   
  81.                 }   
  82.                 System.out.println("no" + i + " output: " + output);   
  83.             }   
  84.             while (!postExpStack.isEmpty()) {   
  85.                 output += postExpStack.pop();   
  86.             }   
  87.             postExpStack.displayStack("final stack is: ");   
  88.             return output;   
  89.         }   
  90.   
  91.         // 根据读取的字符是+-*/的时候做处理   
  92.         private void doOper1(char ch, int num) {   
  93.             while (!postExpStack.isEmpty()) {   
  94.                 char chPop = postExpStack.pop();   
  95.                 if (chPop == '(') {   
  96.                     postExpStack.push(chPop);   
  97.                     break;   
  98.                 } else {   
  99.                     int opernum;   
  100.                     if (chPop == '+' || (chPop == '-')) {   
  101.                         opernum = 1;   
  102.                     } else  
  103.                         opernum = 2;   
  104.   
  105.                     if (num > opernum) {   
  106.                         postExpStack.push(chPop); // 读取的操作符为*/，而栈顶内容为+-，则将*/入栈   
  107.                         break;   
  108.                     } else {   
  109.                         output += chPop;   
  110.                     }   
  111.                 }   
  112.             }   
  113.             postExpStack.push(ch);   
  114.         }   
  115.   
  116.         // 读取的字符为)时的处理方式   
  117.         private void doOper2() {   
  118.             while (!postExpStack.isEmpty()) {   
  119.                 char chPop = postExpStack.pop();   
  120.                 if (chPop == '(') {   
  121.                     break;   
  122.                 } else {   
  123.                     output += chPop;   
  124.                 }   
  125.             }   
  126.         }   
  127.     }   
  128.   
  129.     public static void main(String[] args) {   
  130.         PostExpression pe = new ExpressionCal().new PostExpression(   
  131.                 "(1+(4-6/2))*3");   
  132.         System.out.println("after trans: " + pe.transPostExp());   
  133.     }   
  134.   
  135. }   

 

运行结果如下：

  1. no0 stack is:     
  2. no0 output:    
  3. no1 stack is: (     
  4. no1 output: 1  
  5. no2 stack is: (     
  6. no2 output: 1  
  7. no3 stack is: ( +     
  8. no3 output: 1  
  9. no4 stack is: ( + (     
  10. no4 output: 14  
  11. no5 stack is: ( + (     
  12. no5 output: 14  
  13. no6 stack is: ( + ( -     
  14. no6 output: 146  
  15. no7 stack is: ( + ( -     
  16. no7 output: 146  
  17. no8 stack is: ( + ( - /     
  18. no8 output: 1462  
  19. no9 stack is: ( + ( - /     
  20. no9 output: 1462/-   
  21. no10 stack is: ( +     
  22. no10 output: 1462/-+   
  23. no11 stack is:     
  24. no11 output: 1462/-+   
  25. no12 stack is: *     
  26. no12 output: 1462/-+3  
  27. final stack is:     
  28. after trans: 1462/-+3*   

 

利用最后的结果1462/-+3*就比较容易用栈实现计算了，按顺序读数，数字入栈，当读到操作符后用栈顶两个数做计算，并将结果入栈，所以是1462先入栈，读到/，62出栈做6/2=3，3入栈，读到-，再43出栈做4-3=1，再1入栈，读到+，再11出栈做1+1=2，2入栈，再3入栈，读到*，23出栈做2*3=6为最后结果。

分享到：
| 数据结构之归并排序
评论
2 楼 totty 2008-03-06  
只是一个中缀转换为后缀的解释示例，的确不完善。
1 楼 sithlqf 2008-02-23  
只能一位数转化
发表评论

您还没有登录,请您登录后再发表评论

相关推荐

Magicbox
Global site tag (gtag.js) - Google Analytics