`
totty
  • 浏览: 23410 次
  • 性别: 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  
只能一位数转化

相关推荐

    数据结构(中缀表达式转后缀表达式)

    /*程序由本人编译,并且经过多次测试,正确无误!目前该转换算法只支持数字在0至9之间的+-*/四元运算转换.*/ /**************程序员信息 ***************东北大学*******************东大很厉害**************** ...

    数据结构的中缀表达式转后缀表达式使用C++实现

    本文将详细讨论如何使用C++实现数据结构中的一个重要概念——中缀表达式转化为后缀表达式,也被称为逆波兰表示法。这个过程涉及到堆栈这一重要的数据结构。 中缀表达式是我们日常生活中常见的数学表达式形式,例如 ...

    数据结构 中缀表达式向后缀表达式转换

    本程序用c++编写,实现中缀表达式向后缀表达式转换 其中,中缀表达式的操作数是一位

    数据结构算法:中缀表达式转化为后缀表达式.doc

    数据结构算法:中缀表达式转化为后缀表达式.doc 详细的论述和代码!

    数据结构中缀表达式变后缀表达式计算

    程序用了两个栈实现表达式的计算 根绝算符优先级进行pop push 的到后缀表达式 并输出 然后再根绝所得的后缀表达式计算!

    java数据结构与算法之中缀表达式转为后缀表达式的方法

    栈是一种后进先出(Last In First Out, LIFO)的数据结构,在这里它用于临时存储运算符和括号,直到它们需要被转换到后缀表达式中。 ### 栈的实现 首先,我们需要定义一个栈的数据结构,通常使用一个字符数组和一...

    数据结构课程设计实验报告(后缀表达式的计算).

    数据结构课程设计实验报告的主题是“后缀表达式的计算”,这是一种高效的方法来处理数学表达式。后缀表达式,也称为逆波兰表示法,是一种没有括号的表达式表示方式,其中运算符位于它们的操作数之后。这种表示法在...

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

    这里我们关注的是一个特定的数据结构问题:如何将中缀表达式转换为后缀表达式,也称为逆波兰表示法。中缀表达式是我们日常数学计算中常用的表达方式,比如 `2 + 3 * 4`,而后缀表达式则是运算符放在操作数后面的格式...

    数据结构实验报告-栈与队列-中缀表达式转换为后缀式5分-实验内容及要求.docx

    本次实验是针对西南交通大学计算机科学与技术专业的学生设计的一次实践任务,旨在帮助学生更好地理解并掌握数据结构中栈的应用,特别是栈在处理数学表达式方面的功能。实验的核心任务是将中缀表达式转换为后缀表达式...

    中缀表达式转后缀表达式并计算java

    将一个表达式转为后缀表达式,用堆栈计算 中缀转后缀的过程中遇到数字直接输出,遇到符号则判断优先级。

    中缀表达式转后缀表达式

    用栈实现中缀表达式转为后缀表达式,规定了各个符号的优先级,可以说是对栈概念的深入理解

    栈实现中缀表达式到后缀表达式的转换

    本主题将深入探讨如何使用栈数据结构来实现中缀表达式到后缀表达式的转换,主要以C语言编写。 栈是一种具有“后进先出”(LIFO)特性的数据结构,非常适合处理运算符的优先级。转换过程主要分为两个步骤:扫描中缀...

    哈工大数据结构作业-算数表达式求值

    在哈工大的数据结构课程中,学生被分配了一项作业,任务是实现一个算数表达式求值的程序。这个程序不仅需要处理基本的算数运算,如加法、减法、乘法和除法,还要扩展到处理小数计算以及涉及变量的计算。这个项目旨在...

    后缀表达式相关,包括中缀表达式转后缀表达式以及后缀表达式的运算

    后缀表达式中,数据与数据之间加分隔符; (2) 输出正确的计算结果,保留两位小数点; (3) 考虑算法的健壮性,当表达式错误时,要给出错误提示 (4) 可以连续输入,即输入完一个表达式,转换和计算完成后可以...

    c语言实现中缀表达式向后缀表达式转换

    本篇文章将详细探讨如何通过C语言实现中缀表达式到后缀表达式转换的过程,并具体分析所涉及的关键算法与数据结构。 #### 中缀表达式与后缀表达式简介 - **中缀表达式**:我们日常使用的数学表达式,如 `3 + 4 * 2`...

    C语言实现中缀表达式转化后缀表达式

    利用C语言实现中缀表达式转化为后缀表达式!!利用栈。

    前缀表达式、中缀表达式和后缀表达式 - 乘月归 - 博客园.pdf

    在这种表达式中,运算符位于其对应的操作数之前。例如,中缀表达式"A + B"对应的前缀表达式为"+ A B"。前缀表达式在计算机求值时非常高效,因为不需要考虑运算符的优先级,只需要用栈来处理,按照“从右至左扫描”和...

    数据结构-实验3-后缀表达式求值.doc

    空间复杂度也是 O(n),最坏情况下,当表达式中所有元素都是操作数时,操作数栈和运算符栈可能达到最大深度 n。 实验完成后,需要撰写实验报告,详细记录输入的实验数据、程序运行结果,并以截图形式附在报告中。...

    数据结构实验-算术表达式求值

    通过本次实验,不仅加深了对栈这一数据结构的理解,还学会了如何将抽象的数据结构应用于解决实际问题之中。特别是对于算术表达式的处理,从中缀到后缀的转换以及后缀表达式的求值都是计算机科学中的重要概念,对后续...

    中缀表达式转后缀表达式计算

    在后缀表达式中,运算符位于两个操作数的后面,并且没有括号,其运算符的次序就是其执行运算的次序。后缀表达式计算过程的规则非常简单:从左到右依次扫描,当读到运算符时,就对该运算符前面的两个操作数执行相应的...

Global site tag (gtag.js) - Google Analytics