栈的应用google、百度一大把,这里就弄一个简单的例子:中缀表达式 转 后缀表达式
在中缀表达式(就是我们人类通常写的算术表达式)中,计算需要注意优先级、括号这些问题,和运算符的实际运算次序往往同它们在表达式中的先后次序不一致,所以波兰科学家提出了后缀表达式,把运算符放在两个运算对象的后面。
在后缀表达式中看,不存在括号,也不存在运算符优先级的差别,计算过程完全按照运算符出现的先后次序进行,整个计算过程仅需扫描一遍便可完成。
中缀表达式转换成后缀表达式:
中缀算术表达式转换成对应的后缀算术表达式的规则是:把每个运算符都移到它的两个运算对象的后面,然后删除掉所有的括号即可。
为了转换正确,必须设定一个运算符栈,并在栈底放入一个特殊算符,假定为@,让它具有最低的运算符优先级,此栈用来保存扫描中缀表达式得到的暂不能放入后缀表达式中的运算符,待它的两个运算对象都放入到后缀表达式之后,再令其出栈并写入到后缀表达式中。
转换过程如下:从头到尾扫描中缀表达式,若遇到数字则直接写入后缀表达式,若遇到运算符,则比较栈顶元素和该运算符的优先级,当该运算符的优先级大于栈顶元素的时候,表明该运算符的后一个运算对象还没有进入后缀表达式,应该把该运算符暂存于运算符栈中,然后把它的后一个运算对象写入到后缀表达式中,再令其出栈并写入后缀表达式中;若遇到的运算符优先级小于等于栈顶元素的优先级,表明栈顶运算符的两个运算对象已经被写入后缀表达式,应将栈顶元素出栈并写入后缀表达式,对于新的栈顶元素仍进行比较和处理,直到栈顶元素的优先级小于当前等待处理的运算符的优先级为止,然后令该运算符进栈即可。
按照上述过程扫描到中缀表达式的末尾,把剩余的运算符依次出栈并写入后缀表达式即可。
(对于左括号直接进栈,右括号则使左右两个括号内的运算符都出栈)。
看代码比较省力,如下:
package com.matt.stack;
import java.util.*;
public class Expression {
String expression = "";
public Expression() {
}
public Expression(String _expression) {
this.expression = _expression;
}
public List<String> toRight() {
if(this.expression.equals("")||this.expression == null) throw new NullPointerException();
Stack<String> temp = new Stack<String>();
List<String> list = new ArrayList<String>();
char[] charArray = this.expression.toCharArray();
for (int i = 0; i < charArray.length; i++) {
switch (charArray[i]) {
case '+':
while(!temp.isEmpty()&&!temp.peek().equals("(")){
list.add(temp.pop());
}
temp.push(String.valueOf(charArray[i]));
break;
case '-':
while(!temp.isEmpty()&&!temp.peek().equals("(")){
list.add(temp.pop());
}
temp.push(String.valueOf(charArray[i]));
break;
case '*':
while(!temp.isEmpty()&&(temp.peek().equals("*")||temp.peek().equals("/"))){
list.add(temp.pop());
}
temp.push(String.valueOf(charArray[i]));
break;
case '/':
while(!temp.isEmpty()&&(temp.peek().equals("*")||temp.peek().equals("/"))){
list.add(temp.pop());
}
temp.push(String.valueOf(charArray[i]));
break;
case '(':
temp.push(String.valueOf(charArray[i]));
break;
case ')':
do{
list.add(temp.pop());
}while(!temp.peek().equals("("));
temp.pop();
break;
default:
list.add(String.valueOf(charArray[i]));
break;
}
}
while(!temp.isEmpty())
list.add(temp.pop());
return list;
}
public List<String> toRight(String _expression) {
this.expression = _expression;
return toRight();
}
private String listtoString(List<String> lst){
String toStr = "";
for(String str : lst){
toStr += str;
}
return toStr;
}
public static void main(String[] args) {
Expression ex = new Expression("a+b*c-(d*e+f)/g");
List<String> lst = ex.toRight();
System.out.println(ex.listtoString(lst));
lst = ex.toRight("1+2-5*(5-4)*6-(6-1)");
System.out.println(ex.listtoString(lst));
lst = ex.toRight("1*2/(2+1)*7");
System.out.println(ex.listtoString(lst));
}
}
分享到:
相关推荐
该程序很好实现了算术表达式求值,支持+、-、*、/,以=结束,符合正常表达式。
c++ c 栈的应用--数值转换 数据结构严蔚敏版
嵌入式协议栈uCUSB-Device应用开发——基于STM32微控制器, 嵌入式协议栈uCUSB-Device应用开发——基于STM32微控制器,
同样的是栈的应用-中缀-后缀为了初学者学会数据结构的源码
该源码 详细说明了c语言中 顺序栈在进制转换上的应用
实验二 栈的应用---算术表达式的计算.doc
实验二栈地应用---算术表达式地计算.doc
基本思想: 数制转换方法 N = (Ndiv8)10´ 8+N mod 8 N:十进制数,div:整除运算,mod:求余运算。 计算时从低位到高位顺序产生八进制数的各个数位显示时按从高位到低位的顺序输出
举例说明栈的应用——中缀变后缀。
s140_nrf52_7.2.0_softdevice.hex、s140_nrf52_6.0.0_softdevice.hex等等均可用于NRF52840开发
栈的应用c++代码,中缀表达式转换为后缀表达式。
栈的应用-平衡符号
TI官方协议栈源代码,是学习的好资料!...在通信的接收方数据包依次向上通过协议栈,每一层的实体能够根据预定的格式准确的提取需要在本层处理的数据信息,最终用户应用程序得到最终的数据信息进行处理。
很好的一个迷宫求解程序。此程序用0和1来随机产生一个迷宫,然后用栈的基本操作来实现迷宫的求解。很适合用于数据结构栈应用的课程设计。
电商应用-电商应用系统-电商应用系统源码-电商应用管理系统-电商应用管理系统java代码-电商应用系统设计与实现-基于springboot的电商应用系统-基于Web的电商应用系统设计与实现-电商应用网站-电商应用网站代码-电商...
电商应用-电商应用系统-电商应用系统源码-电商应用管理系统-电商应用管理系统java代码-电商应用系统设计与实现-基于springboot的电商应用系统-基于Web的电商应用系统设计与实现-电商应用网站-电商应用网站代码-电商...
数据结构章节--栈。程序主要功能是实现各种类型表达式的计算。类C语言编程...
实验三 栈的应用 1.实验目的: 熟悉栈的定义,栈的特点以及栈的基本操作。能够根据实际情况选择合适的存储结构,解决实际问题。 2.实验内容: 对任意给定的一个中缀算术表达式,输出等价的后缀形式。