括号的匹配

括号的匹配

括号的匹配问题
简单的分析一下
可以用的括号可以分为以下几种
  • "()"
  • "[]"
  • "{}"
  • "<>"
    匹配过程中又以下四种情况
  • 左右括号乱序
  • 左括号比右括号多
  • 右括号比左括号多
  • 匹配

    算法思路

  • 定义一个栈,根据栈后进先出的特性进行括号匹配
  • 依次读入一个字符当这个字符是左括号时,将其压入栈顶
  • 重复第二步,如果字符时右括号将栈顶元素出栈与当前字符匹配,如果匹配不做任何操作,如果不匹配将这两个字符再次压入栈直到所有字符都处理完。

下面是java代码实现括号匹配算法

  1 package neuq.chao;
  2 
  3 import java.io.BufferedReader;
  4 import java.io.InputStreamReader;
  5 import java.util.Scanner;
  6 
  7 class Stack {
  8     char[] data;
  9     char[] brackets = { '(', ')', '[', ']', '{', '}', '<', '>' };
 10     int maxSize;
 11     int top;
 12     char ch;
 13     Scanner input = new Scanner(System.in);
 14 
 15     public Stack(int maxSize) { // 构造函数
 16         this.maxSize = maxSize;
 17         data = new char[maxSize];
 18         top = -1;
 19     }
 20 
 21     public int getSize() {
 22         return this.maxSize;
 23     }
 24 
 25     public int getElementCount() {
 26         return this.top;
 27     }
 28 
 29     public boolean isEmpty() {    //判断栈空
 30         return top == -1;
 31     }
 32 
 33     public boolean isFull() {       //判断栈满
 34         return top + 1 == maxSize;
 35     }
 36 
 37     public boolean push(char data) {    //入栈操作
 38         if (isFull()) {
 39             System.out.print("栈已满");
 40             return false;
 41         }
 42         this.data[++top] = data;
 43         return true;
 44     }
 45 
 46     public char pop() {           //出栈操作
 47         if (this.isEmpty()) {
 48             System.out.print("栈已空");
 49         }
 50         return this.data[top--];
 51     }
 52 
 53     boolean isBrackets(char ch) {        //判断输入字符是否是括号
 54         int i;
 55         boolean f = false;
 56         for (i = 0; i < 8; i++) {
 57             if (ch == brackets[i]) {
 58                 f = true;
 59                 break;
 60             }
 61             f = false;
 62         }
 63         return f;
 64     }
 65 
 66     void pipei() throws Exception {
 67         Stack stack;
 68         char temp = 0;        //存储临时出战的字符
 69         int match = 0;        //是否完全匹配的标志0不匹配1匹配
 70         stack = new Stack(0);
 71         BufferedReader reader = new BufferedReader(new InputStreamReader(
 72                 System.in));
 73         ch = (char) reader.read();
 74         while (ch != '0') {
 75             while(!isBrackets(ch)){
 76                 ch = (char)reader.read();
 77             }
 78             if (getElementCount() == -1) {
 79                 push(ch);
 80             } else {
 81                 temp = pop();
 82                 match = 0;
 83 
 84                 if (temp == '(' && ch == ')') {
 85                     match = 1;
 86                 }
 87                 if (temp == '[' && ch == ']') {
 88                     match = 1;
 89                 }
 90                 if (temp == '<' && ch == '>') {
 91                     match = 1;
 92                 }
 93                 if (temp == '{' && ch == '}') {
 94                     match = 1;
 95                 }
 96                 if (match == 0) {
 97                     push(temp);
 98                     push(ch);
 99                 }
100 
101             }
102             ch = (char) reader.read();
103         }
104 
105         if (getElementCount() == -1) {
106             System.out.printf("输入的括号完全匹配!
");
107         } else {
108             System.out.printf("输入的括号不匹配,请检查!
");
109         }
110     }
111 }
112 
113 public class PiPei {
114 
115     public static void main(String args[]) throws Exception {
116         Stack s = new Stack(20);
117         System.out.printf("括号匹配问题! 
");
118         System.out.printf("请先输入一组括号组合,以0表示结束。");
119         s.pipei();
120 
121     }
122 
123 }
原文地址:https://www.cnblogs.com/code-changeworld/p/4390921.html