#每周一算法#,今天介绍一下逆波兰表达式的栈实现方式:
概念:
逆波兰表示法也叫后缀表示法,即操作符号都置于操作数的后面,逆波兰表示法可以不用括号来标识操作符的优先级。例如:3+4 是一个中缀表达式,转换成逆波兰表达式为34+ 。有人可能会想有后缀表达式,中缀表达式,那有没有前缀表达式呢?答案是:有前缀表达式,也叫波兰表达式,上文中的3+4 用前缀表达式表示为+34。
用途:
了解了什么是逆波兰表达式,那它有什么具体的用途呢?
1.逆波兰表达式中不需要括号,用户只需按照表达式顺序求值,让堆栈自动记录中间结果;同样的,也不需要指定操作符的优先级
2.机器状态永远是一个堆栈状态,堆栈里是需要运算的操作数,栈内不会有操作符。
3.当有操作符时就计算,因此,表达式并不是从右至左整体计算而是每次由中心向外计算一部分,这样在复杂运算中就很少导致操作符错误。
计算原理:
逆波兰表达式进行数据计算的时候一般分为两步:
1.将中缀表达式转换为后缀表达式
2.对转换完成后的后缀表达式进行计算
例子:我们以a+b-c*(d+e) 来进行分析
第一步:将其转换为后缀表达式
1.首先我们要建立一个集合 sList 来存放例子中的数据和操作符号,一个栈opStack来存放中间的操作符号,一个集合dList 来存放最后的转换结果。
2.从sList中取出一个元素A然后进行以下判断:
1.如果A是数字,则直接存如dList
2.如果A是运算符,则和opStack栈顶的元素进行运算优先级比较
1.如果A的优先级高于栈顶运算符优先级,则将A入栈opStack
2.如果A的优先级低于或等于栈顶运算符的优先级,那么将栈顶的元素出栈存入dList,重复此步骤直到栈顶的运算符优先级低于当前运算符,然后A入栈。
3.如果A是左括号“(”直接入栈,如果是右括号“)”,则将opStack中的运算符弹出存入dList,直到弹出左括号,左右括号均不存入dList,左括号永远不会弹出,直到遇到右括号。
4.不断重复以上步骤直到表达式解析完成。
3.下面来看一下这个具体例子
dList opStack
dList opStack
{} {}
{a} {} //a 加入dList
{a} {+} //+ 入栈
{a,b} {+} //b 加入dList
{a,b,+} {-} //+号出栈,-号入栈
{a,b,+,c} {-} //c 加入dList
{a,b,+,c} {-,*} //因为* 的优先级高于- 则将* 直接入栈
{a,b,+,c} {-,*,(} //左括号直接入栈
{a,b,+,c,d} {-,*,(} //d 加入dList
{a,b,+,c,d} {-,*,(,+} //+ 直接入栈
{a,b,+,c,d,e} {-,*,(,+} //e 直接加入dList
{a,b,+,c,d,e,+} {-,*} //将左括号之上的符号出栈加入dList
{a,b,+,c,d,e,+,*,-} {} //将栈中的剩余元素弹出
将dList 中的元素输出,则得到后缀表达式:ab+cde+*-
第二步:用后缀表达式来计算结果
首先建立一个结果栈rStack,然后将dList中的元素依次取出,进行入栈操作,如果碰到操作符就从栈中取出两个元素进行运算,结果入栈,依次重复。
下面接着看上面的例子
dList {a,b,+,c,d,e,+,*,-}
rStack
{ }
{a} //a入栈
{a,b} //b入栈
{a+b} //遇到+号,取出两个操作数进行运算,运算结果入栈
{a+b,c}
{a+b,c,d}
{a+b,c,d,e}
{a+b,c,d+e}
{a+b,c*(d+e)}
{a+b-c*(d+e)}
计算结果:a+b-c*(d+e)
下面使用代码实现该过程
package com.algorithm;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import java.util.Stack;
import java.util.StringTokenizer;
/**
* 使用栈实现中缀表达式到后缀表达式的转换
* @author 马永华
*
*/
public class ReversePolish {
private List<String> sList = new ArrayList<String>();//中缀表达式集合
private List<String> dList = new ArrayList<String>();//后缀表达式集合
private Stack<String> opStack = new Stack<String>();//操作符栈
private Stack<String> rStack = new Stack<String>();//结果运算栈
private final int level1 = 0;//+-的级别是0
private final int level2 = 1;//*/的级别是1
private final int level3 = 3;//左右括号是3
//初始化
public ReversePolish(String input){
//a+b-c*(d+e) 转换为实际值例如:1+2-3*(4+5)
StringTokenizer st = new StringTokenizer(input, "+-*/()", true);
while(st.hasMoreTokens()){
sList.add(st.nextToken());
}
}
//1.将中缀表达式转换为后缀表达式
private List<String> convertToReversePolish(){
for(String A : sList){
System.out.println(A);
//如果是数字,则直接存入dList
if(isNumber(A))
dList.add(A);
//如果是操作符
else if(isOperate(A))
opstack(A);
else
System.out.println("非法操作符");
}
//将栈清空
while(!opStack.empty()){
dList.add(opStack.pop());
}
return dList;
}
/**
* 对操作符号进行处理
* @param dList
* @param op
*/
private void opstack(String op){
//如果是空栈,则直接压入
if(opStack.empty()){
opStack.push(op);
return;
}
//如果是左括号直接入栈
if("(".equals(op)){
opStack.push(op);
return;
}
//如果op 是右括号则对栈内元素进行出栈操作,直到遇到左括号
if(")".equals(op)){
String tmp = "";
while(!"(".equals(tmp=opStack.pop())){
dList.add(tmp);
}
return;
}
//如果栈顶是左括号,当前操作符号直接入栈
if("(".equals(opStack.peek())){
opStack.push(op);
return;
}
//如果当前操作符的优先级高于栈顶元素,直接入栈
if(comparePriority(op,opStack.peek())){
opStack.push(op);
return;
}
//如果当前元素的优先级低于栈顶元素的优先级
if(!comparePriority(op,opStack.peek())){
//如果栈顶不是左括号则进行出栈操作
dList.add(opStack.pop());
opstack(op);
}
}
//判断是不是数字
private boolean isNumber(String num){
return num.matches("\\d+");
}
//判断是不是操作符
private boolean isOperate(String op){
return op.matches("[\\+\\-\\*\\/\\(\\)]");
}
// 判断op1 的优先级 是否大于 op2的优先级
private boolean comparePriority(String op1,String op2){
return getLevel(op1) > getLevel(op2);
}
//获得操作符的优先级
private int getLevel(String op){
if("+".equals(op)||"-".equals(op)){
return level1;
}
if("*".equals(op)||"/".equals(op)){
return level2;
}
if("(".equals(op)||")".equals(op)){
return level3;
}
return -1;
}
//2.对后缀表达式进行计算
private String calculateReversePolish(){
for(String A:dList){
if(isNumber(A))
rStack.push(A);
//如果是操作符
else if(isOperate(A))
calculate(A);
}
//栈中最后一个元素就是计算结果
return rStack.pop();
}
//取两个操作数进行运算,并将运算结果入栈
private void calculate(String op){
int d2 = Integer.valueOf(rStack.pop());
int d1 = Integer.valueOf(rStack.pop());
if("*".equals(op)){
rStack.push(d1*d2+"");
}else if("/".equals(op)){
rStack.push(d1/d2+"");
}else if("+".equals(op)){
rStack.push(d1+d2+"");
}else if("-".equals(op)){
rStack.push(d1-d2+"");
}
}
public static void main(String args[]){
ReversePolish rp = new ReversePolish("1+((2-3)*(4+5))+((6/2))");
List<String> list = rp.convertToReversePolish();
for(String s : list){
System.out.print(s+",");
}
System.out.println();
System.out.println(rp.calculateReversePolish());
}
}
后缀表达式:123-45+*+62/+
运算结果:-5
分享到:
相关推荐
C语言:设计一个算法,将一般算术表达式转化为逆波兰表达式,并求逆波兰表达式的值。数据结构实验
是个人上数据结构课后,通过4天努力写出的代码文章,可能不是很好,但可用来参考参考!
逆波兰表达式及其算法实现 很好的资料 里面分析很全面
以字符串的形式输入一个算术表达式,转换为逆波兰表达式,并求取其数值。
C语言之逆波兰表达式完整代码(附算法),详细讲解其实现
Leetcode 150. 逆波兰表达式求值问题描述150. 逆波兰表达式求值 - 力扣(LeetCode)算法解法1解法1: 实现:def evalRPN(s
【数据结构与算法】逆波兰表达式完整版,使用java语言编写。逆波兰表达式又叫做后缀表达式,是一种没有括号,并严格遵循“从左到右”运算的后缀式表达方法
表达式求值,逆波兰表达式算法,支持任何位数值运算,运算符支持+-*/(),其它运算符请自行扩展,代码比较松耦合可扩展性好
表达式求值 逆波兰表达式算法,支持任何位数值运算,运算符支持+-*/(),其它运算符请自行扩展,代码比较松耦合可扩展性好
输入中缀表达式转换成逆波兰表达式的值显示出来,并通过转化的逆波兰表达式求出中缀表达式的值,主要利用到栈的原理。
读取输入字符存入数组中,逐个扫描数组元素遇操作数进栈,遇运算符计算并将结果进栈继续上述过程,直至数组读取完
算法-逆波兰表达式(信息学奥赛一本通-T1198)(包含源程序).rar
本文实例讲述了Python实现处理逆波兰表达式。分享给大家供大家参考,具体如下: 中文名: 逆波兰表达式 外文名: Reverse Polish Notation 别名: 后缀表达式 逆波兰表达式又叫做后缀表达式。在通常的表达式中,二元...
逆波兰表达式求值.md
一,逆波兰表达式的介绍 前缀: 前缀表达式又称波兰式,前缀表达式的运算符位于操作数之前 举例说明: (3+4)×5-6 对应的前缀表达式就是 – × + 3 4 5 6 中缀:不再多说。 后缀: 逆波兰表达式,与前缀表达式相似,...
使用C++模拟了计算器的四则运算,包括加减乘除以及括号优先级运算,主要解决办法是将键盘输入的四则运算表达式转为逆波兰表达式,然后再进一步计算逆波兰表达式的值,具体算法思路在主页,资源包括一个main.cpp文件...
利用栈和逆波兰式实现算术表达式求值。程序运行正确。
本文主要对Java算法逆波兰表达式的相关内容作了介绍,涉及逆波兰表达式的定义已经在Java中的实现,具有一定参考价值,需要的朋友可以了解下。
(1)建立两个栈,一个S1用来存放操作符+ - * / ( ),另一个S2用来存放生成的逆波兰表达式(本文中为了方便用一个字符串来存放逆波兰表达式),操作符栈遵循越往栈顶操作符优先级越高的原则。 (2)从中缀表达式的...
设计一个算法判别一个算术表达式的圆括号是否正确配对