1.用数组实现简单的栈
package stack;
/**
* 用数组实现栈
*/
public class ArrayStack {
/**
* 定义一个数组
*/
private int[] stack;
// 定义数组长度
private int maxSize;
// 定义栈顶指针
private int top = -1;
public ArrayStack(int maxSize) {
this.maxSize = maxSize;
stack = new int[maxSize];
}
// 判断栈空
public boolean isEmpty() {
return this.top == -1;
}
// 判断栈满
public boolean isFully() {
return this.top == this.maxSize - 1;
}
// 压栈
public void push(int val) {
// 判断是否栈满
if (isFully()) {
throw new RuntimeException("栈满");
}
top++;
stack[top] = val;
}
// 弹栈
public int pop() {
// 判断是否栈空
if (isEmpty()) {
throw new RuntimeException("栈空");
}
int val = stack[top];
top--;
return val;
}
// 查看所有元素
public void list() {
// 判断是否栈空
if (isEmpty()) {
throw new RuntimeException("栈空");
}
for (int i = 0; i < stack.length; i++) {
System.out.println(stack[i]);
}
}
// 返回栈的长度
public int length() {
return top + 1;
}
// 判断是否是运算符
public boolean isOpera(char a) {
return a == '+' || a == '-' || a == '*' || a == '/';
}
// 获取栈顶元素
public int peek() {
return stack[this.top];
}
// 获取当前栈的长度
public int stackLength() {
return stack.length;
}
// 判断运算符的优先级
public int priority(int oper) {
if (oper == '/' || oper == '*') {
return 1;
}
return 0;
}
// 计算两数之间的运算结果
public int caculate(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;
default:
break;
}
return result;
}
}
2.利用栈判断回文字符串
package stack;
import javax.naming.InitialContext;
public class HwStack {
public static void main(String[] args) {
System.out.println(isHuiWen("aaa"));
System.out.println(isHuiWen("abababab"));
}
public static boolean isHuiWen(String val) {
// 初始化栈对象
ArrayStack stack = new ArrayStack(10);
// 获取字符串长度
int length = val.length();
// 压栈
for (int i = 0; i < length; i++) {
stack.push(val.charAt(i));
}
// 出栈
int length1 = stack.length();
String str = "";
for (int i = 0; i < length1; i++) {
// 判断非空
if (!stack.isEmpty()) {
char s = (char)stack.pop();
str += s;
}
}
if (val.equals(str)){
return true;
}
return false;
}
}
3.利用栈计算表达式
package stack;
import sun.applet.Main;
public class JsStack {
public static void main(String[] args) {
String str = "4+3*2*2-1";
/**
* 1.需要遍历字符串，获取每一个字符
* 2.判断当前字符是一个运算符还是数字
* 3.把数字存放在数字栈中，把运算符放在运算符栈中
* 4.运算符栈：如果是一个空栈，那么直接运算符入栈，如果运算符栈中已经有了其他运算符
* 就需要先对比运算符优先级大小，即将入栈的运算符的优先级如果小于等于原栈顶运算符的优先级，
* 那么需要将数字栈中的数字弹栈出两个进行运算，运算后的结果再次放入数字栈中，然后即将入栈的运算符入栈。
* 如果即将入栈的运算符优先级大于原来栈顶的运算符的优先级，则直接入栈、
*/
/**
* 初始化数字栈和运算符栈
*/
ArrayStack numStack = new ArrayStack(10);
ArrayStack symbolStack = new ArrayStack(10);
// 两个运算数
int temp1 = 0;
int temp2 = 0;
// 运算符
int symbolChar = 0;
// 结果
int result = 0;
int length = str.length();
String values = "";
for (int i = 0; i < length; i++) {
char c = str.charAt(i);
// 判断是否是一个运算符
if (symbolStack.isOpera(c)) {
// 如果是一个运算符
// 比较运算符等级
if (!symbolStack.isEmpty()) {
if (symbolStack.priority(c) <= symbolStack.priority(symbolStack.peek())) {
/**
* 如果即将入栈的运算符的优先级小于等于栈顶运算符的优先级
* 弹出栈顶运算符，数字栈弹出两个数字进行运算
*/
temp1 = numStack.pop();
temp2 = numStack.pop();
symbolChar = symbolStack.pop();
result = numStack.caculate(temp1, temp2, symbolChar);
// 运算结果压入数字栈
numStack.push(result);
// 当前运算符压入符号栈
symbolStack.push(c);
} else {
// 如果即将入栈的运算符的优先级大于原来栈顶运算符的优先级，则直接入栈
symbolStack.push(c);
}
} else {
symbolStack.push(c);
}
} else {
// 如果是一个数字
// 如果数字不是一位数则需要进行拼接
values += c;
// 如果当前数字是字符串最后一位就直接入栈
if (i == length - 1) {
numStack.push(Integer.parseInt(values));
} else {
// 取到当前数字的下一位
char data = str.substring(i + 1, i + 2).charAt(0);
if (symbolStack.isOpera(data)) {
numStack.push(Integer.parseInt(values));
values = "";
}
}
}
}
while (true) {
if (symbolStack.isEmpty()) {
break;
}
temp1 = numStack.pop();
temp2 = numStack.pop();
symbolChar = symbolStack.pop();
result = numStack.caculate(temp1, temp2, symbolChar);
numStack.push(result);
}
int res = numStack.pop();
System.out.println("结果是：" + res);
}
}
|