概述

在OJ上会遇到一些这样的题目：

小明同学写数学四则运算，有把括号写多、写少、写错的情况，比如（A+B)*(C-D ，请你输入一个表达式，判断此表达式的括号是否正确(不考虑运算的结果正确性)。

每次我看到 "括号"、算数表达式，我的第一反应就是栈、树遍历，逆波兰表达式这些概念。

此文，我们就来探讨一下这类算法的使用。

一、栈

此处我就不想太过深入的讲解其原理了，都是数据结构基础，知道它是FILO的就行了。

栈本质上来说，是一个线性表，存储结构可以是顺序的（连续内存划分），也可以是链表

栈是允许在同一端进行插入和删除操作的特殊线性表。

允许进行插入和删除操作的一端称为栈顶(top)，另一端为栈底(bottom)；

栈底固定，而栈顶浮动；

栈中元素个数为零时称为空栈。

插入一般称为进栈（PUSH），删除则称为退栈（POP）。栈也称为先进后出表。

1、我们在什么情况下会用到栈？

在JVM中，我们常听说虚拟机栈的概念，虚拟机栈是存在于运行时数据区的一个逻辑单元，它由一个个栈帧（Stack frame）构成，在当前线程中，每进行一次函数调用，就会形成一个栈帧。当进行一次方法调用，虚拟机会压入一个栈帧、方法结束的时候，会弹出该栈帧。

比如方法 m1，m2, m3

m3 调用m2 ，m2 调用m1，我们进行一次测试：

package com.huawei.oj;/*** @Title:* @Description: Method called ，JVM stack Frame struct* @author: Alex* @Version:* @date 2023-01-22-8:20*/
public class StackDemo {public static void main(String[] args) {m3();}public static int m1(){System.out.println("m1 开始");int i=10;System.out.println("m1 结束");return i;}public static int m2(){System.out.println("m2开始");int i = m1();System.out.println("m2结束");return i;}public static int m3(){System.out.println("m3开始");int i = m2();System.out.println("m3结束");return i;}
}

Debug我们看到，函数调用（压栈）顺序 Main---->m3 ------>m2---->m1

输出结果，我们也能看到压栈和弹栈的顺序，也是满足 FILO的：

2、为什么说到栈？

前面说的这道题，最典型的解题思路，就是栈。

思路：

判断表达式的括号是否正确：

1、括号的数量是对称相等的（这一步判断并不是必须的，因为2，和3 其实可以完全涵盖1）

2、每个左括号，后面必然有一个右括号等待与之匹配

3、不能以右括号）开头，或者以左括号）结尾

这里对第二点进行补充：

左括号之后并不一定就是右括号，因为会有括号嵌套的现象，比如 ((A+B）*C) -D)

满足上述几个条件后，我们用栈去解答如何设计算法：

设计算法：

1、遍历表达式字符串

2、遇见左括号就压栈，

3、遇见右括号，先判断栈是否为空，不为空就弹栈，为空，直接返回“表达式书写错误”

4、遍历完成，判断栈是否为空，为空，返回表示表达式正确，不为空，说明栈内还有左括号，返回表达式书写错误

具有代码实现：

package com.huawei.oj;import java.util.Scanner;
import java.util.Stack;/*** @Title:* @Description: TODO* @author: Alex* @Version:* @date 2023-01-22-8:48*/
public class Express {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);String str = scanner.nextLine();Stack<String> stack = new Stack<>();for(int i=0;i<str.length();i++){boolean isempty = stack.isEmpty();boolean isEqualR = ')'==str.charAt(i);boolean isEqualL = '('==str.charAt(i);if(isempty&&isEqualR) {  //空栈，右括号开头，或者多了一个右括号System.out.println("表达式不正确");return;}if(isEqualL){ //遇见左括号 压栈stack.push("(");}if(!isempty&&isEqualR){  //正常匹配，遇见右括号 弹栈stack.pop();}}if(stack.isEmpty()){ //输出判定： 最终栈空 正确 ；非空 括号数量不对System.out.println("表达式正确");}elseSystem.out.println("表达式不正确");}
}