栈
2019-03-02 本文已影响0人
carrot_4d8d
栈模型(LIFO)
限制插入和删除只能在一个位置进行的表，即栈顶操作。
基本操作
- push()
- pop()
- top()
栈的实现
ArrayList和LinkedList都支持栈操作。可以使用链式结构或者使用数组。
栈的应用
- 平衡符号
package top.carrotguo.stack.apply;
import com.sun.org.apache.xerces.internal.impl.xpath.regex.Match;
import top.carrotguo.bean.stack.Stack;
/**
* 括号匹配
* @Author: Carrot
* @Mail: 1053155183carrot@gmail.com
* @Date: Created in 13:14 2018-06-10
*/
public class Matching {
//表达式
private String expression;
private String e;
//简化后只有括号的表达式
private String simple="";
private Stack<Character> stack;
public Matching(String expression){
this.expression = expression;
stack = new Stack<>();
}
/**
* 简化表达式只保存括号
*/
private void simply(){
for (int i=0; i<expression.length(); i++) {
if (expression.charAt(i)=='('
|| expression.charAt(i)==')'
|| expression.charAt(i)=='['
|| expression.charAt(i)==']'
|| expression.charAt(i)=='{'
|| expression.charAt(i)=='}') {
simple += expression.charAt(i);
}
}
System.out.println(simple);
}
/**
* 括号匹配
*/
public boolean isMatch(){
//简化表达式（留括号）
simply();
for (int i=0; i<simple.length(); i++) {
char e = simple.charAt(i);
if (e == '(' || e == '[' || e == '{') {
//左括号进栈
stack.push(e);
} else if (!stack.isEmpty()) {
//右括号且栈非空 出栈一个左括号
if (e==')'&&stack.top()=='(') {
stack.pop();
} else if (e==']' && stack.top()=='[') {
stack.pop();
} else if (e=='}' && stack.top()=='{') {
stack.pop();
}
} else {
//右括号还存在 但栈已空 无法匹配
return false;
}
}
return stack.isEmpty();
}
public static void main(String[] args){
Matching matching = new Matching("{[(3+1)*(3+6)]+(3-5)}+(3+5)");
boolean isMatch = matching.isMatch();
if (isMatch) {
System.out.println("匹配成功");
} else {
System.out.println("匹配失败");
}
}
}
- 进制转换
package top.carrotguo.stack.apply;
import top.carrotguo.bean.stack.Stack;
/**
* 进制转换
* @Author: Carrot
* @Mail: 1053155183carrot@gmail.com
* @Date: Created in 22:09 2018-06-09
*/
public class Conversion {
//进制对应数字的表示形式（如十六进制的10写为A）
private String[] digit = {"0","1","2","3","4","5","6","7","8","9","A","B","C","D","E","F"};
//存储余数的栈
private Stack<String> remainder = new Stack();
/**
* 进制转换
* @param n
* @param base base进制
*/
public void convert(int n,int base){
String result = null;
while (n>0) {
//余数进栈
remainder.push(digit[n%base]);
n /= base;
}
System.out.print(n+"进行"+base+"进制转换 >>> ");
while ((result=remainder.pop()) != null) {
System.out.print(result+" ");
}
}
public static void main(String[] args){
Conversion conversion = new Conversion();
conversion.convert(257,16);
}
}
- 后缀表达式（逆波兰式）求值
package top.carrotguo.leetcode.stack;
import java.util.Stack;
/**
* 后缀表达式求值
* @Author: Carrot
* @Mail: 1053155183carrot@gmail.com
* @Date: Created in 20:52 2018-07-18
*/
public class Solution {
private Stack<Integer> numStack = new Stack();
private Stack<Character> optrStack = new Stack();
public int evalRPN(String[] tokens) {
for(String str : tokens){
if(!str.equals("+")&&!str.equals("-")&&!str.equals("*")&&!str.equals("/")){
numStack.push(Integer.valueOf(str));
} else {
switchCalu(str);
}
}
return numStack.pop();
}
private void switchCalu(String op){
int num2 = numStack.pop();
int num1 = numStack.pop();
int result = 0;
switch(op){
case "+":{
result = num1+num2;
break;
}
case "-":{
result = num1-num2;
break;
}
case "*":{
result = num1*num2;
break;
}
case "/":{
result = num1/num2;
break;
}
}
numStack.push(result);
}
public static void main(String[] args){
Solution solution = new Solution();
int result1 = solution.evalRPN(new String[]{"2","1","+","3","*"});
int result2 = solution.evalRPN(new String[]{"4","13","5","/","+"});
System.out.println(result1);
System.out.println(result2);
}
}
- 中缀表达式转后缀表达式
package top.carrotguo.stack.apply;
import top.carrotguo.bean.stack.Stack;
import java.util.regex.Pattern;
/**
* 中缀表达式转后缀表达式
* @Author: Carrot
* @Mail: 1053155183carrot@gmail.com
* @Date: Created in 21:08 2018-06-13
*/
public class InfixToPostfix {
private String iExpression; //中缀表达式
private Stack<Float> opnd; //数字栈
private Stack<Character> optr; //符号栈
private String pExpression = ""; //后缀表达式
//优先级表
private char[][] pri = {/*----------------当前运算符----------------------*/
/*+ - * / ^ ! ( ) \0*/
/*-- + */ {'>','>','<','<','<','<','<','>','>'}
/*| - */,{'>','>','<','<','<','<','<','>','>'}
/*栈 * */,{'>','>','>','>','<','<','<','>','>'}
/*顶 / */,{'>','>','>','>','<','<','<','>','>'}
/*运 ^ */,{'>','>','>','>','>','<','<','>','>'}
/*算 ! */,{'>','>','>','>','>','>',' ','>','>'}
/*符 ( */,{'<','<','<','<','<','<','<','=',' '}
/*| ) */,{' ',' ',' ',' ',' ',' ',' ',' ',' '}
/*--\0 */,{'<','<','<','<','<','<','<',' ','='}};
/**
* @param express 中缀表达式
*/
public InfixToPostfix(String express){
iExpression = express+'\0';
//初始化栈
opnd = new Stack<>();
optr = new Stack<>();
}
/**
* 中缀表达式转后缀表达式
* @return 后缀表达式
*/
public String conver(){
optr.push('\0'); //表达式起始符号进栈,用于控制所有符号出栈并且判断是否扫描完整个表达式
int index = 0; //当前扫描表达式的字符的索引
char e; //当前扫描表达式的字符
//中缀表达式转后缀表达式
while (!optr.isEmpty()) {
e = iExpression.charAt(index);
//数字则读取数字并且追加到后缀表达式
if (isNum(e)) {
//读取数字 扫描的位置定位到下一个符号位置
index = readNum(index)+1;
pExpression += opnd.top()+" ";
} else {
//操作符处理
//1 根据优先级处理
//2 将index定位 进行下一轮循环
index = switchOperate(optr.top(),index);
}
}
return pExpression;
}
/**
* 根据优先级处理符号
* @param top 栈顶符号
* @param index 当前扫描的符号
* @return 下一次循环应该扫描的位置
*/
private int switchOperate(char top, int index){
char e = iExpression.charAt(index);
char priority = orderBetween(top,e); //获取优先级比较
//根据优先级不同进行处理
switch (priority) {
case '<' : {
//栈顶元素优先级低于当前扫描符-->直接进栈,下一次扫描位置后移一位
optr.push(e);
index++;
break;
}
case '=' : {
//')'或者'\0'情况-->只需栈顶弹栈,下一次扫描位置后移一位
optr.pop();
index++;
break;
}
case '>' : {
//栈顶元素弹栈，追加到后缀表达式中,下一次扫描位置不变
pExpression += optr.pop()+" ";
break;
}
}
return index;
}
/**
* 返回优先级比较
* @param top 栈顶符号
* @param e 当前扫描符号
* @return > < =
*/
private char orderBetween(char top, char e){
String digit = "+-*/^!()\0";
int topIndex = digit.indexOf(top);
int eIndex = digit.indexOf(e);
return pri[topIndex][eIndex];
}
/**
* 判断是否是数字
* @param c
* @return
*/
private boolean isNum(char c){
String num = "0123456789";
if (num.indexOf(c) != -1) {
return true;
}
return false;
}
private boolean isNum(String str){
Pattern pattern = Pattern.compile("[0-9]+([.]{1}[0-9]+){0,1}");
return pattern.matcher(str).matches();
}
/**
* 数字转换
* @param index
* @return 返回连续的最后一位数字
*/
private int readNum(int index){
float num = Float.parseFloat(String.valueOf(iExpression.charAt(index)));
//判断下一位是否为数字
if (isNum(iExpression.charAt(index+1))) {
//index后移一位
index++;
num = num*10+Float.parseFloat(String.valueOf(iExpression.charAt(index+1)));
}
//数字进栈
opnd.push(num);
return index;
}
/**
* 根据后缀表达式计算
* @return 表达式结果
*/
public float calculate(String[] postFix){
float sum = 0;
//先清空数字栈
while (!opnd.isEmpty()) {
opnd.pop();
}
for (String str : postFix) {
if (isNum(str)) {
//数字进栈
opnd.push(Float.valueOf(String.valueOf(str)));
} else {
//直接计算
if (str == "!") {
//单操作数运算
float num = opnd.pop();
num = switchPower(num);
//计算结果重新入栈
opnd.push(num);
} else {
//双操作数运算
float num2 = opnd.pop();
float num1 = opnd.pop();
char op = str.charAt(0); //此时str必定是操作符 取第一个元素转化为char即为操作符
float result = switchCalcu(num1,num2,op);
//计算结果入栈
opnd.push(result);
}
}
}
sum = opnd.top();
return sum;
}
/**
* 根据运算符计算(二元)
* @return
*/
public float switchCalcu(float num1,float num2, char operator){
float result = 0;
switch (operator) {
case '+' : {
result = num1+num2;
break;
}
case '-' : {
result = num1 - num2;
break;
}
case '*' : {
result = num1 * num2;
break;
}
case '/' : {
result = num1 / num2;
break;
}
case '^' : {
result = (float) Math.pow(num1,num2);
break;
}
}
return result;
}
/**
* 根据运算符计算（一元）
* @return
*/
public float switchPower(float num){
float sum = 1;
for (int i=1; i<=num; i++) {
sum *= i;
}
return sum;
}
public static void main(String[] args){
InfixToPostfix infixToPostfix = new InfixToPostfix("(1+2)+5^2+(6-1)");
//System.out.println(infixToPostfix.conver());
String[] str = infixToPostfix.conver().split(" ");
for (String s: str) {
System.out.print(s+" ");
}
float result = infixToPostfix.calculate(str);
System.out.print("="+result);
}
}
- 中缀表达式求值
package top.carrotguo.stack.apply;
import top.carrotguo.bean.stack.Stack;
/**
* 栈应用——中缀表达式求值
* @Author: Carrot
* @Mail: 1053155183carrot@gmail.com
* @Date: Created in 17:14 2018-06-10
*/
public class InfixExpression {
private char[][] pri = { /*当前运算符*/
/*+ - * / ^ ! ( ) \0*/
/*-- + */ {'>','>','<','<','<','<','<','>','>'}
/*| - */,{'>','>','<','<','<','<','<','>','>'}
/*栈 * */,{'>','>','>','>','<','<','<','>','>'}
/*顶 / */,{'>','>','>','>','<','<','<','>','>'}
/*运 ^ */,{'>','>','>','>','>','<','<','>','>'}
/*算 ! */,{'>','>','>','>','>','>',' ','>','>'}
/*符 ( */,{'<','<','<','<','<','<','<','=',' '}
/*| ) */,{' ',' ',' ',' ',' ',' ',' ',' ',' '}
/*--\0 */,{'<','<','<','<','<','<','<',' ','='}};
private Stack<Character> optr; //运算符栈
private Stack<Float> opnd; //运算数栈
private String expression; //表达式
public InfixExpression(String expression){
optr = new Stack<>();
opnd = new Stack<>();
//末尾加上'\0', '\0' 用于控制所有操作符出栈
this.expression = expression+'\0';
}
/**
* 中缀表达式结算——栈的应用
* @return
*/
public float evaluate(){
//先将表达式开始标识符'\0'进栈
optr.push('\0');
int i=0; //记录当前扫描到的字符
//扫描表达式
while (!optr.isEmpty()) {
//是否为数字
if (isDigit(expression.charAt(i))) {
//数字进栈（多位数需要进行处理为一个数字再入栈）
i = readNum(i);
i++; //扫描下一位
} else { //当前扫描到的为运算符
//根据优先级处理(scan为扫描过且已进栈的符号个数)
char top = optr.top();
int scan = switchOperate(top,expression.charAt(i));
i += scan;
}
}
return opnd.top();
}
/**
* 根据优先级计算
* @param top 操作符栈顶元素
* @param e 当前扫描到的操作符
*/
private int switchOperate(char top,char e){
int scan = 0; //进栈操作符个数
char priority = orderBetween(top,e);
switch (priority) {
case '<' : {
//栈顶优先级<当前扫描符号--操作符进栈
optr.push(e);
scan = 1;
break;
}
case '=' : {
//栈顶优先级=当前扫描符号--操作符弹栈，扫描表达式下一位(有括号或者\0)
optr.pop();
scan = 1;
break;
}
case '>' : {
char op = optr.pop(); //弹出栈顶操作符
//单目操作符
if (op == '!') {
opnd.push(calcu(op,opnd.pop()));
} else {
//双目操作符
float num2 = opnd.pop();
float num1 = opnd.pop();
opnd.push(calcu(num1,num2,op));
}
scan = 0;
break;
}
}
return scan;
}
/**
* 单目运算
* @param op
* @param num
* @return 运算结果
*/
private float calcu(char op, float num){
float sum = 1;
if (op == '!') {
for (int i=1; i<=num; i++) {
sum *= i;
}
}
return sum;
}
/**
* 双目运算
* @param num1 第一个操作数
* @param num2 第二个操作数
* @param op 操作符
* @return 结果
*/
private float calcu(float num1, float num2, char op){
float result = 0;
switch (op) {
case '+' : {
result = num1 + num2;
break;
}
case '-' : {
result = num1 - num2;
break;
}
case '*' : {
result = num1 * num2;
break;
}
case '/' : {
result = num1 / num2;
break;
}
case '^' : {
result = (float) Math.pow(num1,num2);
}
}
return result;
}
/**
* 优先级比较（栈顶？当前扫描运算符）
* @return > < =
*/
private char orderBetween(char top, char e){
String digit = "+-*/^!()\0";
int topIndex = digit.indexOf(top);
int scanDidex = digit.indexOf(e);
return pri[topIndex][scanDidex];
}
/**
* 判断字符是否为数字
* @param e
* @return
*/
private boolean isDigit(char e){
String num = "0123456789";
if (num.indexOf(e)!=-1) {
return true;
}
return false;
}
/**
* 数字转化并进栈（因为多位数是多个字符组成 需要转化为float）
* @param i 当前扫描到表达式的位置
* @return 扫描到的最后一个连续数字的位置
*/
private int readNum(int i){
float num = Float.parseFloat(String.valueOf(expression.charAt(i)));
//判断表达式下一位是否是数字，是数字则要进行转换
while (isDigit(expression.charAt(i+1))) {
i++;
num = num*10+Float.parseFloat(String.valueOf(expression.charAt(i)));
}
//数字进栈
opnd.push(num);
return i;
}
public static void main(String[] args){
InfixExpression infixExpression = new InfixExpression("(1+2)+5^2+(6-1)");
float result = infixExpression.evaluate();
System.out.println("计算结果 >> "+result);
}
}
