一 问题描述

假设一个表达式由英文字母（小写）、运算符（+、-、*、/）和左右小圆括号构成，以“@”作为表达式的结束符（表达式的长度小于 255，左括号少于 20 个）。请编写一个程序检查表达式中的左右圆括号是否匹配，若匹配，则返回“YES”，否则返回“NO”。

输入：每一个测试用例都对应一行表达式。

输出：对每个测试用例都单行输出“YES”或“NO”。

输入样例
2*（x+y）/(1-x)@

(25+x)(a(A+b+b))@

输出样例

YES

NO

二 思路

只有左右小圆括号，可以将左圆括号入栈，遇到右圆括号，弹出栈顶的左圆括号，如果栈空，则说明右圆括号多了。如果在表达式处理完毕后，在栈中还有元素，则说明左圆括号多了。结果是大写的“YES”或“NO”，不要写成小写的。

三 设计

1 初始化一个栈 s。

2 读取字符 c，如果 c!='@',则执行第 3 步，否则转向第 5 步。

3 如果 c='('，则入栈 s.push(c)。

4 如果 c=')',则判断栈是否为空，如果栈非空，则出栈，否则输出“NO”,结束。

5 在字符处理完毕，判断栈是否为空，如果栈为空，则说明正好配对，输出“YES”，否则输出“NO”，结束。

四 图解

1 以样例 2*(x+y)/(1-x)@ 为例，初始化一个栈，如下图所示。

2 读入字符 2*( ，遇到左圆括号入栈。

3 继续读入 x+y)，遇到右圆括号，如果栈非空，则出栈。

4 继续读入 /( ,遇到左圆括号时入栈。

5 继续读入 1-x，遇到右圆括号，如果栈非空，则出栈。

6 继续读入“@”，遇到“@”，字符串读入完毕，此时栈为空，说明括号匹配，输出“YES”。

五 实现

package stackdemo;

import java.util.Scanner;
import java.util.Stack;

public class StackDemo {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        Character c;
        Stack<Character> s = new Stack<>();
        while (true) {
            String input = scanner.next();
            for (int i = 0; i < input.length(); i++) {
                c = input.charAt(i);
                if (c == '(') {
                    s.push(c);
                }
                if (c == ')') {
                    if (!s.empty()) {
                        s.pop();
                    } else {
                        System.out.println("NO");
                        return;
                    }
                }
            }
            if (s.empty()) {
                System.out.println("YES");
            } else {
                System.out.println("NO");
            }
        }
    }
}

六 测试

绿色为输入，白色为输出。