栈
后进先出
1. 顺序栈
- 定义栈顶top，初始值为-1
- 入栈：stack[++top] = data
- 出栈：return stack[top--]
- 栈空：top == -1
- 栈满：top == capacity - 1
public class MyStack<E> {
// 栈的最大容量
private int capacity;
// 采用数组实现栈
private E[] stack;
// 栈顶索引
private int top = -1;
public MyStack(int capacity) {
this.capacity = capacity;
stack = (E[]) new Object[capacity];
}
public boolean empty() {
return top == -1;
}
public boolean full() {
return top == capacity - 1;
}
public int size() {
return top + 1;
}
public E push(E item) {
if (full()) {
throw new RuntimeException("full");
}
// 先将top++，在赋值
stack[++top] = item;
return item;
}
public E pop() {
if (empty()) {
throw new RuntimeException("empty");
}
// 先获取栈顶值，再将top--
return stack[top--];
}
public E peek() {
if (empty()) {
throw new RuntimeException("empty");
}
return stack[top];
}
}
2. 中缀表达式
利用栈计算中缀表达式结果思路：
- 从左至右遍历中缀表达式，依次取出表达式的每一个字符
- 若取出的字符是运算符：
- 如果符号栈为空，直接入符号栈
- 如果符号栈不为空，判断当前操作符与栈顶操作符的优先级
- 当前操作符优先级小于或等于栈顶操作符：计算，然后将当前操作符压入符号栈
- 当前操作符优先级大于栈中的操作符，直接入符号栈
- 若取出的字符是操作数：分析出完整的运算数
- 如果当前已经是最后一位，则入栈
- 如果下一个字符是符号，则入栈
- 计算，直到符号栈为空
- 最后数字栈中仅剩的数字就是表达式结果
- 计算过程：
- 从数字栈pop出两个数
- 从符号栈顶pop出一个符号
- 计算，将运算结果压入数字栈
中缀表达式代码实现：
import java.util.Stack;
public class Calculator {
// 获取符号优先级
public static int priority(char operation) {
if (operation == '*' || operation == '/')
return 1;
else if (operation == '+' || operation == '-')
return 0;
else
return -1;
}
// 判断字符是否为符号
public static boolean isOperation(char value) {
return value == '+' || value == '-' || value == '*' || value == '/';
}
// 计算 left operation right
public static int calc(int left, int right, int operation) {
int result = 0;
switch (operation) {
case '+':
result = left + right;
break;
case '-':
result = left - right;
break;
case '*':
result = left * right;
break;
case '/':
result = left / right;
break;
}
return result;
}
public static void main(String[] args) {
String expression = "320+200*5-12/2";
// 数字栈
Stack<Integer> numStack = new Stack<>();
// 符号栈
Stack<Character> opeStack = new Stack<>();
int left, right, result;
char ch = ' ', operation;
String curNum = "";
// 从左至右遍历中缀表达式，依次取出表达式的每一个字符
for (int i = 0; i < expression.length(); i++) {
ch = expression.charAt(i);
// 若取出的字符是运算符
if (isOperation(ch)) {
// 如果符号栈为空，直接入符号栈
if (opeStack.empty()) {
opeStack.push(ch);
} else {
// 如果符号栈不为空，判断当前操作符与栈顶操作符的优先级
// 当前操作符优先级小于或等于栈顶操作符
if (priority(ch) <= priority(opeStack.peek())) {
// 从数字栈pop出两个数
right = numStack.pop();
left = numStack.pop();
// 从符号栈顶pop出一个符号
operation = opeStack.pop();
// 进行运算
result = calc(left, right, operation);
// 将运算结果压入数字栈
numStack.push(result);
// 将当前操作符压入符号栈
opeStack.push(ch);
} else {
// 当前操作符优先级大于栈中的操作符，直接入符号栈
opeStack.push(ch);
}
}
} else {
// 若取出的字符是操作数：分析出完整的运算数
curNum += ch;
// 如果当前已经是最后一位，则入栈
if (i == expression.length() - 1) {
numStack.push(Integer.parseInt(curNum));
curNum = "";
} else if (isOperation(expression.charAt(i + 1))) {
// 如果下一个字符是符号，则入栈
numStack.push(Integer.parseInt(curNum));
// 清空curNum
curNum = "";
}
}
}
// 从数字栈取出两个数，从符号栈取出一个符号，计算，直到符号栈为空
while (!opeStack.empty()) {
right = numStack.pop();
left = numStack.pop();
operation = opeStack.pop();
result = calc(left, right, operation);
numStack.push(result);
}
// 最后数字栈中仅剩的数字就是表达式结果
// 320+200*5-12/2=1314
System.out.println(expression + "=" + numStack.pop());
}
}
3. 中缀转后缀
中缀表达式转换为逆波兰表达式的思路：
- 初始化两个栈：运算符栈o和结果栈r
- 从左至右遍历中缀表达式，依次取出表达式的每一个字符
- 若取出的字符是操作数，则将该操作数压入r栈
- 若取出的字符是左括号'('，直接压入o
- 若取出的字符是右括号')'，则依次弹出o栈顶运算符，并压入r，直到遇到左括号为止，此时将这一对括号丢弃
- 若取出的字符是运算符：
- 若o为空或栈顶运算符为左括号'('，则直接将运算符压入o
- 若当前运算符优先级比栈顶运算符高，则直接将运算符压入o
- 若当前运算符优先级比栈顶运算符低，将o栈中优先级比当前运算符优先级高的运算符压入到r栈中，再将当前运算符压入o栈
- 将o中剩余的运算符依次弹出并压入r
- 依次弹出r中元素并输出，结果的逆序即中缀表达式对应的后缀表达式
后缀表达式计算器代码实现：
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
// 逆波兰表达式计算器
public class ReversePolishCalculator {
public static void main(String[] args) {
String expression = "(3*(300+100)+200)/2+614";
List<String> infixExpressionList = toInfixExpressionList(expression);
List<String> suffixExpressionList = parseSuffixExpressionList(infixExpressionList);
// 中缀表达式：[(, 3, *, (, 300, +, 100, ), +, 200, ), /, 2, +, 614]
System.out.println("中缀表达式：" + infixExpressionList);
// 后缀表达式：[3, 300, 100, +, *, 200, +, 2, /, 614, +]
System.out.println("后缀表达式：" + suffixExpressionList);
// 计算结果：1314
System.out.println("计算结果：" + calc(suffixExpressionList));
}
// 1. 将中缀表达式转为对应的List
public static List<String> toInfixExpressionList(String s) {
List<String> list = new ArrayList<>();
// 用于遍历中缀表达式
int i = 0;
// 用于拼接数字
String num;
// 存放遍历到的字符
char c;
do {
c = s.charAt(i);
// 如果c不是数字，加入到list中
if (c < '0' || c > '9') {
list.add("" + c);
i++;
} else {
// 如果是一个数字，需要考虑多位数
num = "";
while (i < s.length() && '0' <= (c = s.charAt(i)) && c <= '9') {
num += c;
i++;
}
list.add(num);
}
} while (i < s.length());
return list;
}
// 2. 将中缀表达式对应的List转换为后缀表达式对应的List
public static List<String> parseSuffixExpressionList(List<String> list) {
Stack<String> oStack = new Stack<>(); // 符号栈
// r栈在转换过程中没有pop操作
Stack<String> rStack = new Stack<>();
// 从左至右遍历中缀表达式，依次取出表达式的每一个字符
for (String item : list) {
if (item.matches("\\d+")) {
// 若取出的字符是操作数，则将该操作数压入r栈
rStack.push(item);
} else if (item.equals("(")) {
// 若取出的字符是左括号'('，直接压入o
oStack.push(item);
} else if (item.equals(")")) {
// 若取出的字符是右括号')'，则依次弹出o栈顶运算符，并压入r，直到遇到左括号为止，此时将这一对括号丢弃
while (!oStack.peek().equals("(")) {
rStack.push(oStack.pop());
}
// )未在栈中，不用丢弃；丢弃(
oStack.pop();
} else {
// 若优先级比栈顶运算符低：
// 将o栈中优先级比当前运算符优先级高的，压入到r栈中
while (oStack.size() != 0 && priority(item) < priority(oStack.peek())) {
rStack.push(oStack.pop());
}
// 若o为空，则不会执行上面的循环
// 若栈顶运算符为左括号'('，则priority(oStack.peek()为-1，不会执行上面的循环
// 若当前运算符优先级比栈顶运算符高，则不会执行上面的循环
// 将当前运算符压入o栈
oStack.push(item);
}
}
// 将o中剩余的运算符依次弹出并压入r
while (oStack.size() != 0) {
rStack.push(oStack.pop());
}
return rStack;
}
// 3. 对逆波兰表达式的计算
public static int calc(List<String> list) {
Stack<String> stack = new Stack<>();
int result = 0;
for (String item : list) {
// 如果是数字：入栈
if (item.matches("\\d+")) {
stack.push(item);
} else {
// 是运算符：pop出两个数，计算，然后入栈
int right = Integer.parseInt(stack.pop());
int left = Integer.parseInt(stack.pop());
if (item.equals("+"))
result = left + right;
else if (item.equals("-"))
result = left - right;
else if (item.equals("*"))
result = left * right;
else if (item.equals("/"))
result = left / right;
else {
throw new RuntimeException("运算符有误");
}
// 将result入栈
stack.push("" + result);
}
}
// 最后留在栈里的就是结果
return Integer.parseInt(stack.pop());
}
// 获取符号优先级
public static int priority(String operation) {
if ("*".equals(operation) || "/".equals(operation))
return 1;
else if ("+".equals(operation) || "-".equals(operation))
return 0;
else
return -1;
}
}
