思路:
遇到数字,则输出。
遇到操作符,入栈,在入栈前若该操作符优先级较低或与栈中优先级相同则将栈中操作符弹出,输出。
遇到左括号入栈,直到遇到右括号,将左括号之前的操作符弹出,输出。弹出左括号。
例子:
a + b * c + (d * e + f ) * g
输出 |
栈 |
备注 |
ab |
+ |
|
abc |
+* |
*优先级大于+所以入栈 |
abc*+ |
+ |
+优先级小于*等于+所以* +出栈,+入栈 |
abc*+ |
+( |
(具有最高优先级,入栈 |
abc*+de |
+(* |
(只有遇到)才会弹出 |
abc*+de*f |
+(+ |
+优先级小于*,*出栈,+入栈 |
abc*+de*f+ |
+ |
遇到)将斩重元素弹出直到( |
abc*+de*f+g |
+* |
*优先级大于+所以*入栈 |
abc*+de*f+g*+ |
|
最后将栈中符号全部弹出 |
代码:
栈类
package cn.edu.tju.postfix;
public class Stack {
private int maxSize;
private int top;
private char[] stack;
public Stack(int maxSize){
this.maxSize = maxSize;
this.stack = new char[maxSize];
this.top = -1;
}
public void push(char c){
stack[++top] = c;
}
public char pop(){
return stack[top--];
}
public boolean isEmpty(){
return top == -1;
}
public char getTop(){
return stack[top];
}
}
核心实现类
package cn.edu.tju.postfix;
public class InToPost {
private String input;
private String output = "";
private Stack stack;
public InToPost(String input){
this.input = input;
stack = new Stack(input.length());
}
public String doTrans(){
for(int i = 0; i < input.length(); i ++){
char ch = input.charAt(i);
switch(ch){
case '*':
case '/':
while(!stack.isEmpty() && (stack.getTop() == '*' || stack.getTop() == '/')){
output += stack.pop();
}
stack.push(ch);
break;
case '+':
case '-':
while(!stack.isEmpty() && stack.getTop() != '('){
output += stack.pop();
}
stack.push(ch);
break;
case '(':
stack.push(ch);
break;
case ')':
char temp;
while(!stack.isEmpty() && ((temp = stack.pop()) != '(')){
output += temp;
}
break;
default:
output += ch;
break;
}
}
while(!stack.isEmpty()){
output += stack.pop();
}
return output;
}
}
客户端调用类
package cn.edu.tju.postfix;
public class Client {
public static void main(String[] args){
String infix = "a+b*c+(d*e+f)*g";
//infix = "a+b-c*d+e/f";
InToPost ip = new InToPost(infix);
String postfix = ip.doTrans();
System.out.println(postfix);
}
}
分享到:
相关推荐
### 自定义栈中缀表达式转换为后缀表达式并求值 #### 需求分析与背景 在计算机科学领域,将一个中缀表达式转换为后缀表达式是解决算术表达式求值问题的一种常用方法。通过这种方式可以避免括号带来的优先级问题,...
本主题将深入探讨如何使用栈数据结构来实现中缀表达式到后缀表达式的转换,主要以C语言编写。 栈是一种具有“后进先出”(LIFO)特性的数据结构,非常适合处理运算符的优先级。转换过程主要分为两个步骤:扫描中缀...
利用C语言实现中缀表达式转化为后缀表达式!!利用栈。
用栈实现中缀表达式转为后缀表达式,规定了各个符号的优先级,可以说是对栈概念的深入理解
c语言实现中缀表达式转后缀表达式并求得计算结果,用顺序栈结构。 当输入者输入错误信息的时候需要报错,并说明错误的种类。
### C语言实现中缀表达式向后缀表达式转换 #### 概述 在计算机科学领域,表达式的处理是一项基础而重要的任务。表达式通常有三种形式:前缀(波兰)、中缀(标准数学表达式)和后缀(逆波兰)。本篇文章将详细探讨...
总之,这个实验报告的核心是实现中缀表达式到后缀表达式的转换以及基于后缀表达式的计算,它涉及到数据结构中的栈操作,以及对运算符优先级的理解。这个过程对于理解计算机如何解析和计算数学表达式非常有帮助。
一个简单的算法,利用栈实现中缀表达式与后缀表达式的转换
编译系统对中缀表达式的处理方法是先把它转换为后后缀表达式.在后缀表达式中,运算符位于两个操作数的后面,并且没有括号,其运算符的次序就是其执行运算的次序。后缀表达式计算过程的规则非常简单:从左到右依次扫描,...
通过上述分析,我们可以看到Java实现中缀表达式到后缀表达式的转换以及后续的计算涉及到了栈数据结构的应用,以及对各种运算符优先级的正确处理。这种转换方法不仅能够简化表达式的计算流程,还能有效支持包括多位...
在本项目中,“java堆栈的应用--中缀表达式转换成后缀表达式和计算”具体涉及到了两个主要知识点:中缀表达式的转换与后缀表达式的计算。 1. **中缀表达式**:这是我们常见的数学表达式形式,如 `2 + 3 * 4`,其中...
本文将详细讨论如何使用C++实现数据结构中的一个重要概念——中缀表达式转化为后缀表达式,也被称为逆波兰表示法。这个过程涉及到堆栈这一重要的数据结构。 中缀表达式是我们日常生活中常见的数学表达式形式,例如 ...
前缀表达式、中缀表达式和后缀表达式是编程中常见的三种表达式表示方法,它们在计算机程序设计和算法中扮演着重要的角色。中缀表达式是最常见的一种,例如在普通的算术运算中就广泛使用。而后缀表达式和前缀表达式则...
中缀表达式转换为后缀表达式_C++程序设计 中缀表达式转换为后缀表达式是一个常见的数据结构和算法问题。中缀表达式是一种常见的数学表达式表示形式,例如:a \* (x + y) / (b - x),而后缀表达式是将运算符移到它的...
6. **代码参考**:提供的代码`基于栈实现的将中缀表达式转换为后缀表达式.cpp`可能包含了上述逻辑。通过阅读和理解代码,可以更好地掌握这一算法的实现细节,并进行实际编程实践。 这个转换过程在解析和计算复杂...
首先,中缀表达式转后缀表达式的算法通常使用栈数据结构实现。步骤如下: 1. 初始化一个空栈。 2. 从左到右扫描中缀表达式: - 如果当前字符是操作数,直接输出。 - 如果当前字符是运算符,比较它与栈顶运算符的...
将一个表达式转为后缀表达式,用堆栈计算 中缀转后缀的过程中遇到数字直接输出,遇到符号则判断优先级。
`buildRPN` 方法将中缀表达式解析成后缀表达式,该方法使用栈来存储运算符,并根据运算符的优先级来确定其位置。 中缀表达式求值的应用非常广泛,例如计算器程序、科学计算软件等。掌握中缀表达式求值的算法和实现...
在处理这类表达式时,我们通常需要将其转换或直接解析为后缀表达式(也称为逆波兰表示法),因为后缀表达式更适合于简单的栈操作进行求值。然而,通过巧妙地利用栈结构,我们也可以直接对中缀表达式进行求值。本文将...