public class ArrayStackDemo {
public static void main(String[] args) {
ArrayStack arrayStack = new ArrayStack(3);
arrayStack.push(1);
arrayStack.push(2);
arrayStack.push(3);
arrayStack.list();
System.out.println("====");
arrayStack.pop();
arrayStack.list();
}
}
class ArrayStack{
private int maxSize;//栈大小
private int[] stack;//数组存放数据
private int top = -1;//栈顶
public ArrayStack(int maxSize){
this.maxSize = maxSize;
this.stack = new int[maxSize];
}
//判断栈顶，是否栈满
public boolean isFull(){
return this.top == maxSize-1;
}
//判断栈，是否为空
public boolean isFree(){
return this.top == -1;
}
//入栈
public void push(int value){
if (isFull()){
System.out.println("栈满了");
return;
}
top++;
stack[top] = value;
}
//出栈
public int pop(){
if (isFree()){
throw new RuntimeException("栈为空");
}
int vale = stack[top];
top--;
return vale;
}
//显示栈
public void list(){
if (isFree()){
throw new RuntimeException("栈为空");
}
//反向遍历
for (int i = top; i >=0; i--) {
System.out.println(stack[i]);
}
}
}
三、前缀/中缀/后缀表达式 1、前缀表达式
四、栈实现综合计算器（中缀表达式） 1、只能处理单位数的版本
以下的实现方式无法处理多位数的情况
package com.achang.stack;
public class Calculator {
public static void main(String[] args) {
//表达式
String expression = "3+2*6-3";
//创建两个栈，一个是数栈，一个是表达式栈
ArrayStack2 numStack = new ArrayStack2(10);
ArrayStack2 operStack = new ArrayStack2(10);
//定义需要的相关变量
int index = 0;//用于扫描表达式的索引
int num1 = 0;
int num2 = 0;
int oper = 0;
int result = 0;
char ch = ' ';//将每次扫描的得到的char保存到ch中
while (true) {
//依次得到expression中每一个字符
ch = expression.substring(index, index + 1).charAt(0);
//判断ch是什么来做相应的处理
if (operStack.isOper(ch)) {//【如果是运算符】
//判断符号栈是否为空
if (operStack.isFree()) {
operStack.push(ch);
} else {
//如果符号栈有操作符，就进行比较，如果当前的操作符的优先级小于或者等于符号栈中的操作符，就需要从数栈中pop两个数，
//在从符号栈中pop一个符号，进行运算，计算出结果，并将结果push到数栈中，然后把当前的操作符加入到符号栈中
if (operStack.rank(ch) <= operStack.rank(operStack.peek())) {
num1 = numStack.pop();
num2 = numStack.pop();
oper = operStack.pop();
result = numStack.calculate(num1, num2, oper);
numStack.push(result);
operStack.push(ch);
} else {
//如果当前的操作符优先级大于栈中的操作符，就直接入符号栈
operStack.push(ch);
}
}
} else {//【如果是数字】
numStack.push(ch - 48);//将ASCII玛的数字转为对应的数值
}
//让index+1，并判断是否扫描到expression最后了
index++;
if (index >= expression.length()){
break;
}
}
//当表达式扫描完毕后，就顺序从数栈和符号栈中pop出相应的数和符号，并运行
while (true){
//如果符号栈为空，则计算结束，数栈中只有一个数字，且是最后计算的结果
if (operStack.isFree()){
break;
}
num1 = numStack.pop();
num2 = numStack.pop();
oper = operStack.pop();
result = numStack.calculate(num1, num2, oper);
numStack.push(result);
}
System.out.printf("表达式 %s = %d",expression,numStack.pop());
}
}
//栈
class ArrayStack2 {
private int maxSize;//栈大小
private int[] stack;//数组存放数据
private int top = -1;//栈顶
public ArrayStack2(int maxSize) {
this.maxSize = maxSize;
this.stack = new int[maxSize];
}
//查看栈顶的元素，但不弹出栈
public int peek() {
return stack[top];
}
//返回运算符优先级,优先级越大，数字越大
public int rank(int oper) {
if (oper == '*' || oper == '/') {
return 1;
} else if (oper == '+' || oper == '-') {
return 0;
} else {
return -1;//目前假定只有 +-*/符号
}
}
//判断是否是运算符
public boolean isOper(char val) {
return val == '+' || val == '-' || val == '/' || val == '*';
}
//计算方法
public int calculate(int num1, int num2, int oper) {
int result = 0;
switch (oper) {
case '+':
result = num1 + num2;
break;
case '-':
result = num2 - num1;
break;
case '*':
result = num1 * num2;
break;
case '/':
result = num2 / num1;
break;
}
return result;
}
//判断栈顶，是否栈满
public boolean isFull() {
return this.top == maxSize - 1;
}
//判断栈，是否为空
public boolean isFree() {
return this.top == -1;
}
//入栈
public void push(int value) {
if (isFull()) {
System.out.println("栈满了");
return;
}
top++;
stack[top] = value;
}
//出栈
public int pop() {
if (isFree()) {
throw new RuntimeException("栈为空");
}
int vale = stack[top];
top--;
return vale;
}
//显示栈
public void list() {
if (isFree()) {
throw new RuntimeException("栈为空");
}
//反向遍历
for (int i = top; i >= 0; i--) {
System.out.println(stack[i]);
}
}
}
2、多位数处理
package com.achang.stack;
public class Calculator {
public static void main(String[] args) {
//表达式
String expression = "30+2*6-3";
//创建两个栈，一个是数栈，一个是表达式栈
ArrayStack2 numStack = new ArrayStack2(10);
ArrayStack2 operStack = new ArrayStack2(10);
//定义需要的相关变量
int index = 0;//用于扫描表达式的索引
int num1 = 0;
int num2 = 0;
int oper = 0;
int result = 0;
char ch = ' ';//将每次扫描的得到的char保存到ch中
String keepNum = "";//用过拼接多位数
while (true) {
//依次得到expression中每一个字符
ch = expression.substring(index, index + 1).charAt(0);
//判断ch是什么来做相应的处理
if (operStack.isOper(ch)) {//【如果是运算符】
//判断符号栈是否为空
if (operStack.isFree()) {
operStack.push(ch);
} else {
//如果符号栈有操作符，就进行比较，如果当前的操作符的优先级小于或者等于符号栈中的操作符，就需要从数栈中pop两个数，
//在从符号栈中pop一个符号，进行运算，计算出结果，并将结果push到数栈中，然后把当前的操作符加入到符号栈中
if (operStack.rank(ch) <= operStack.rank(operStack.peek())) {
num1 = numStack.pop();
num2 = numStack.pop();
oper = operStack.pop();
result = numStack.calculate(num1, num2, oper);
numStack.push(result);
operStack.push(ch);
} else {
//如果当前的操作符优先级大于栈中的操作符，就直接入符号栈
operStack.push(ch);
}
}
} else {//【如果是数字】
//numStack.push(ch - 48);//将ASCII玛的数字转为对应的数值
keepNum += ch;
//如果ch已经是expression的最后一位，则直接入栈
if (index == expression.length() - 1) {
numStack.push(Integer.parseInt(keepNum));
} else {
//判断下一个字符是不是数字，如果是数字，则继续扫描，如果是运算符，则入数栈
//往后面看一位，不是index++
if (operStack.isOper(expression.substring(index + 1, index + 2).charAt(0))) {
//如果后一位是运算符，则入栈
numStack.push(Integer.parseInt(keepNum));
keepNum = "";//清空
}
}
}
//让index+1，并判断是否扫描到expression最后了
index++;
if (index >= expression.length()) {
break;
}
}
//当表达式扫描完毕后，就顺序从数栈和符号栈中pop出相应的数和符号，并运行
while (true) {
//如果符号栈为空，则计算结束，数栈中只有一个数字，且是最后计算的结果
if (operStack.isFree()) {
break;
}
num1 = numStack.pop();
num2 = numStack.pop();
oper = operStack.pop();
result = numStack.calculate(num1, num2, oper);
numStack.push(result);
}
System.out.printf("表达式 %s = %d", expression, numStack.pop());
}
}
//栈
class ArrayStack2 {
private int maxSize;//栈大小
private int[] stack;//数组存放数据
private int top = -1;//栈顶
public ArrayStack2(int maxSize) {
this.maxSize = maxSize;
this.stack = new int[maxSize];
}
//查看栈顶的元素，但不弹出栈
public int peek() {
return stack[top];
}
//返回运算符优先级,优先级越大，数字越大
public int rank(int oper) {
if (oper == '*' || oper == '/') {
return 1;
} else if (oper == '+' || oper == '-') {
return 0;
} else {
return -1;//目前假定只有 +-*/符号
}
}
//判断是否是运算符
public boolean isOper(char val) {
return val == '+' || val == '-' || val == '/' || val == '*';
}
//计算方法
public int calculate(int num1, int num2, int oper) {
int result = 0;
switch (oper) {
case '+':
result = num1 + num2;
break;
case '-':
result = num2 - num1;
break;
case '*':
result = num1 * num2;
break;
case '/':
result = num2 / num1;
break;
}
return result;
}
//判断栈顶，是否栈满
public boolean isFull() {
return this.top == maxSize - 1;
}
//判断栈，是否为空
public boolean isFree() {
return this.top == -1;
}
//入栈
public void push(int value) {
if (isFull()) {
System.out.println("栈满了");
return;
}
top++;
stack[top] = value;
}
//出栈
public int pop() {
if (isFree()) {
throw new RuntimeException("栈为空");
}
int vale = stack[top];
top--;
return vale;
}
//显示栈
public void list() {
if (isFree()) {
throw new RuntimeException("栈为空");
}
//反向遍历
for (int i = top; i >= 0; i--) {
System.out.println(stack[i]);
}
}
}
五、逆波兰计算器（后缀表达式）
package com.achang.stack;
import java.util.Arrays;
import java.util.List;
import java.util.Objects;
import java.util.Stack;
public class PolandNotation {
public static void main(String[] args) {
//定义一个逆波兰表达式
//( 3 + 4 ) * 5 - 6 = 3 4 + 5 * 6 -
String suffixexpression = "3 4 + 5 * 6 -";
List strings = toList(suffixexpression);
System.out.println(calculate(strings));
}
//将逆波兰表达式，转成一个ArrayList
public static List toList(String suffixexpression){
if (Objects.equals(suffixexpression, "")){
return null;
}
String[] split = suffixexpression.split(" ");
return Arrays.asList(split);
}
//逆波兰表达式的运算
public static int calculate(List list){
Stack stack = new Stack<>();
for (String item : list) {
//判断正则表达式取出数
if (item.matches("\d+")){//匹配多位数
//入栈
stack.push(item);
}else {//运算符
int num1 = Integer.parseInt(stack.pop());
int num2 = Integer.parseInt(stack.pop());
int result = 0;
switch (item) {
case "+":
result = num1 + num2;
break;
case "-":
result = num2 - num1;
break;
case "*":
result = num1 * num2;
break;
case "/":
result = num2 / num1;
break;
default:
throw new RuntimeException("运算符有误");
}
stack.push(String.valueOf(result));
}
}
return Integer.parseInt(stack.pop());
}
}
六、中缀表达式—>后缀表达式 1、思路
2、代码实现
public static void main(String[] args) {
//中缀表达式 ---> 后缀表达式
// 1 + ( ( 2 + 3 ) * 4 ) - 5 => 1 2 3 + 4 * + 5 -
String middleexpression = "1 + ( ( 2 + 3 ) * 4 ) - 5";
List lastexpressionList = getLastexpressionByMiddleexpression(middleexpression);
System.out.println(lastexpressionList);
//根据中缀表达式 ---> 后缀表达式
private static List getLastexpressionByMiddleexpression(String middleexpression) {
List middleexpressionList = Arrays.asList(middleexpression.split(" "));
Stack s1 = new Stack<>();//符号栈
ArrayList s2 = new ArrayList<>();
for (String item : middleexpressionList) {
if (item.matches("\d+")){//判断是否为数字
s2.add(item);
}else if ("(".equals(item)){
s1.push(item);
}else if (")".equals(item)){
while (!s1.peek().equals("(")){
s2.add(s1.pop());
}
s1.pop();
}else{
//当item的优先级小于等于栈顶运算符，将s1栈顶的运算符弹出压入s2，反复执行
while (s1.size() != 0 && getValue(s1.peek()) >= getValue(item)){
s2.add(s1.pop());
}
//将item压入s1栈
s1.push(item);
}
}
//将s1中剩下的元素加入到s2中
while (s1.size()!=0){
s2.add(s1.pop());
}
return s2;
}
//获取运算符优先级
private static int getValue(String item) {
switch (item){
case "+":
return 1;
case "-":
return 1;
case "*":
return 2;
case "/":
return 2;
default:
System.out.println("该运算符不存在");
return 0;
}
}
