java括号匹配算法求解（用栈实现）

java括号匹配算法求解（用栈实现）

如何使用栈来判定括号是否匹配

对于给定的表达式，可以使用栈来实现括号匹配判定，这个算法在编译器中非常重要，解析器每次读入

一个字符，如果字符是一个开分隔符，如（，【，{，入栈，若读入的是闭分隔符），】，},出栈，如果两者匹配，继续解析字符串，如果不匹配，解析器错误

算法思路

1.创建一个栈

2.当（当前字符不等于输入的结束字符）

（1）如果当前字符不是匹配的字符，判断栈内是否为空，如果栈为空，括号必然不完整

（2）如果字符是一个开分隔符，那么将其入栈

（3）如果字符是一个闭分隔符，，且栈不为空，则判断是否匹配

（4）栈结束后判断是否为空，不为空则括号匹配错误

代码示例

class Solution {

public boolean isValid(String s) {

//声明匹配词典

Map map = new HashMap<>();

map.put(')', '(');

map.put(']', '[');

map.put('}', '{');

//创建栈

Stack stack = new Stack<>();

for (char ch : s.toCharArray()) {

//开分隔符入栈

if (ch == '(' || ch == '[' || ch == '{') {

stack.push(ch);

}

//出栈并且栈非空进行匹配

ehttp://lse if (stack.isEmpty() || stack.pop() != map.get(ch)){

return false;

}

}

//如果栈非空则括号匹配错误

return stack.isEmpty();

}

}

下面是其他同学的补充

1.括号匹配算法

//括号匹配算法

public void pipei()throws Exception{

char temp,ch;

int match; //记录匹配结果

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

ch=(char) br.read(); //输入一个字符

while(ch!='0'){

if(getTop()==-1){

push(ch);

}else{

temp=pop(); //取出栈顶元素

match=0; //判断是否匹配（默认不匹配）

if(temp=='('&&ch==')')

match=1;

if(temp=='['&&ch==']')

match=1;

if(temp=='{'&&ch=='}')

match=1;

if(temp=='<'&&ch=='>')

match=1;

if(match==0){ //如果不匹配

push(temp); //将原栈顶元素重新入栈

push(ch); //将输入的括号字符入栈

}

}

ch=(char) br.read(); //输入下一个字符

}

if(isEmpty()){

System.out.println("输入的括号完全匹配！");

}else{

System.out.println("输入的括号不匹配，请检查！");

}

}

2.括号匹配求解示例

package com.cn.datastruct;

import java.io.BufferedReader;

import java.io.InputStreamReader;

import java.util.Scanner;

public class KuoHaoPiPei {

static class Stack{

char[] data; //存放数据

int MaxSize; //最大容量

int top; //栈顶指针

//构造方法

public Stack(int MaxSize){

this.MaxSize=MaxSize;

data = new char[MaxSize];

top = -1;

}

public int getMaxSize() {

return MaxSize;

}

public int getTop() {

return top;

}

public boolean isEmpty(){

return top==-1;

}

public boolean isFull(){

return top+1==MaxSize;

}

//入栈

public boolean push(char data){

if(isFull()){

System.out.println("栈已满!");

return false;

}

this.data[++top]=data;

return true;

}

//出栈

public char pop() throws Exception{

if(isEmpty()){

throw new Exception("栈已空！");

}

return this.data[top--];

}

//获得栈顶元素

public char peek(){

return this.data[getTop()];

}

//括号匹配算法

public void pipei()throws Exception{

char temp,ch;

int match; //记录匹配结果

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

ch=(char) br.read(); //输入一个字符

while(ch!='0'){

if(getTop()==-1){

push(ch);

}else{

temp=pop(); //取出栈顶元素

matchhttp://=0; //判断是否匹配（默认不匹配）

if(temp=='('&&ch==')')

match=1;

if(temp=='['&&ch==']')

match=1;

if(temp=='{'&&ch=='}')

CrLTZ match=1;

if(temp=='<'&&ch=='>')

match=1;

if(match==0){ //如果不匹配

push(temp); //将原栈顶元素重新入栈

push(ch); //将输入的括号字符入栈

}

}

ch=(char) br.read(); //输入下一个字符

}

if(isEmpty()){

System.out.println("输入的括号完全匹配！");

}else{

System.out.println("输入的括号不匹配，请检查！");

}

}

}

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

String go;

Scanner input = new Scanner(System.in);

Stack stack = new Stack(20);

System.out.println("括号匹配问题！");

do{

System.out.println("请输入一组括号的组合，以0表示结束。支持的括号包括：{},(),[],<>。");

stack.pipei(); //匹配算法

System.out.print("\n继续匹配吗（y/n）?");

go=input.next();

}while(go.equalsIgnoreCase("y"));

System.out.println("匹配结束！");

}

}

程序运行结果如下：

括号匹配问题！

请输入一组括号的组合，以0表示结束。支持的括号包括：{},(),[],<>。

({[]})<>0

输入的括号完全匹配！

继续匹配吗（y/n）?y

请输入一组括号的组合，以0表示结束。支持的括号包括：{},(),[],<>。

({])0

输入的括号不匹配，请检查！

继续匹配吗（y/n）?n

匹配结束！

补充2

#include

#include

using namespace std;

#define MAXSIZE 20

typedef struct {

char *base;

char *top;

int stacksize;

}SqStack;

void InitStack(SqStack &S)

{

S.base = (char *)malloc( MAXSIZE * sizeof(char) );

if(S.base == NULL) exit(-2);

S.top = S.base;

S.stacksize = MAXSIZE;

}

void GetTop(SqStack S, char &e)

{

if(S.top == S.base)

return;

e = *(S.top - 1);

}

void Push(SqStack &S, char e) // 不考虑栈满

{

*S.top++ = e;

}

void Pop(SqStack &S, char &e)

{

if(S.top == S.base)

return;

S.top--;

e = *S.top;

}

bool Match(char c, SqStack &my_stack, bool &tag)

{

char e;

Pop(my_stack, e);

if ( c != e ) {

tag = false;

free(my_stack.base);

return false; // match fail

}

return true; // match success

}

void Correct(char *expr, bool &tag)

{

tag = true;

SqStack my_stack;

InitStack (my_stack);

for( int i = 0; expr[i] != '\0'; i++ ) {

char c = expr[i];

switch(c) {

case '{' : case '[' : case '(' :

Push (my_stack, c); break;

case '}' :

if( Match('{', my_stack, tag) == false ) // match fail

return;

break;

case ']' :

if( Match('[', my_stack, tag) == false ) // match fail

return;

break;

case ')' :

if( Match('(', my_stack, tag) == false ) // match fail

return;

break;

default :

break; // 其它字符

}

}

if(my_stack.top != my_stack.base) // e.g.: "[r"

tag = false;

free(my_stack.base);

}

int main(void)

{

// freopen("cin.txt", "r", stdin);

char my_expr[MAXSIZE];

while(cin >> my_expr) {

bool tag = true;

Correct( my_expr, tag);

tag ? printf("匹配成功\n") : printf("匹配失败\n");

}

return 0;

}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。