《Java数据结构与算法》笔记-CH4-3用栈实现分隔符匹配

import java.io.BufferedReader;

import java.io.IOException;

import java.io.InputStreamReader;

/**

 * 利用栈来实现分隔符匹配： 分隔符包括{},[], (),每个左分隔符要和右分隔符匹配，也就是说每个'{'后面要有'}'来匹配，以此类推。

 * 同时，在字符串中后出现的左分隔符应该比早出现的左分隔符要先完成匹配。 例如：c[d] //correct a{b[cd]e} //correct

 * a[b{c}]} //incorrect a{b[c)} //incorrect a{b[c] //incorrect

 *

 * 算法思想：逐个读取字符串字符： 读到非分隔符字符，继续； 读到左分隔符，就入栈；

 * 读到右分隔符，就和从栈顶弹出的左分隔符进行匹配，若不匹配，就返回false；若匹配就继续进行； 如果读到最后，栈中有剩余，则返回false。

 */

class StackB {

	private int maxSize;

	private char[] array;

	private int top;

	public StackB(int size) {

		maxSize = size;

		array = new char[maxSize];

		top = -1;

	}

	public void push(char ch) {

		array[++top] = ch;

	}

	public char pop() {

		return array[top--];

	}

	public char peek() {

		return array[top];

	}

	public boolean isEmpty() {

		return top == -1;

	}

	public boolean isFull() {

		return top == maxSize;

	}

}

class BracketCheck {

	private String input;

	public BracketCheck(String in) {

		input = in;

	}

	/**

	 * 匹配检查

	 * @return

	 */

	public boolean check() {

		int len = input.length();

		StackB stack = new StackB(len);

		for (int i = 0; i < len; i++) {

			char c = input.charAt(i);

			switch (c) {

			case '{':

			case '[':

			case '(':// 如果读到左分隔符，进行入栈操作

				stack.push(c);

				break;

			case '}':

			case ']':

			case ')':// 读到右分隔符

				if (stack.isEmpty()) {// 如果栈为空，说明多出来的右分隔符在栈中没有与之匹配的分隔符，就返回false

					System.out.println("error! " + c + " at " + i);

					return false;

				} else {

					char ch = stack.pop();// 如果栈不空，就进行pop出栈

					// 如果出栈的左分隔符ch和读到的右分隔符c不匹配，就返回false

					if ((ch == '{' && c != '}') || (ch == '[' && c != ']') || (ch == '(' && c != ')')) {

						System.out.println("error! " + c + " at " + i);

						return false;

					}

				}

				break;

			default:

				break;

			}

		}

		if (stack.isEmpty())

			return true;

		return false;

	}

}

public class BracketApp {

	public static void main(String[] args) throws IOException {

		String input;

		while (true) {

			System.out.println("please input string containing delimiters: ");

			System.out.flush();

			input = getString();

			if (input.equals(""))// 读到直接回车换行停止循环

				break;

			BracketCheck bc = new BracketCheck(input);

			System.out.println(bc.check());

		}

	}

	/**

	 * 读取字符串

	 *

	 * @return

	 * @throws IOException

	 */

	public static String getString() throws IOException {

		InputStreamReader isr = new InputStreamReader(System.in);

		BufferedReader reader = new BufferedReader(isr);

		return reader.readLine();

	}

}
巴特西

《Java数据结构与算法》笔记-CH4-3用栈实现分隔符匹配

最新文章

热门文章
