Я должен написать свой собственный стек, используя массив, который затем должен реализовать задачу сопоставления скобок.
Это мой алгоритм: если нам дана строка: "(())" оно возвращает «не сбалансировано», когда оно должно сказать, что оно «сбалансировано». Если вы посмотрите на BracketCheck. java ближе к концу, он проверяет, пуст ли стек, где, если он есть, должен вернуть true и сказать, что данная строка: "(())" сбалансирована. У меня проблемы с отладкой, и результат операции неверен.
Вот мой стек и код основного класса:
public class Stack {
// instance fields:
private char array[]; // our array
private int topOfStack; // this indicates the value for each position
// overloaded constructor:
public Stack(int size) {
this.array = new char[size]; // here we instantiate a new char type array.
this.topOfStack = -1; // we set the starting position of the topOfStack to -1.
}
// push method:
public void push(char character) {
if(isFull() == true) {
System.out.println("Stack overflow error.");
}
else {
topOfStack++;
array[topOfStack] = character;
}
}
// pop method:
public char pop() {
if(isEmpty() == true) {
//System.out.println("Overflow.");
return '\0';
}
else {
char c = array[topOfStack];
topOfStack--;
return c;
}
}
// top method:
public int top() {
if(isEmpty() == true) {
System.out.println("The stack is empty.");
return 0;
}
else {
return array[topOfStack]; // returns the top element in the stack.
}
}
// size method:
public int size() {
return topOfStack + 1;
}
// isEmpty method:
public boolean isEmpty() {
if(topOfStack == -1) {
return true;
}
else {
return false;
}
}
// isFull method:
public boolean isFull() {
if(topOfStack == array.length -1 ) {
System.out.println("Stack if full.");
return true;
}
else {
return false;
}
}
BracketCheck. java
public class BracketCheck {
public static void main(String args[]) {
String text = "(())";
//boolean check = isBalanced(text);
if(isBalanced(text) == true) {
System.out.println("Balanced.");
}
else {
System.out.println("Not balanced");
}
}
public static boolean isBalanced(String text) {
Stack stack = new Stack(25); // for simplicity our stack is going to be a size of 25.
char[]arr = text.toCharArray(); // convert our string to a set of characters in an array.
// here we are looping through our text
for(int i = 0; i < arr.length; i++) {
if(arr[i] == '{' || arr[i] == '(' || arr[i] == '[') {
stack.push(arr[i]);
}
else if(arr[i] == '}' || arr[i] == ')' || arr[i] == ']') {
if(stack.isEmpty()) {
return false; // if empty then return false.
}
else if((stack.pop() == '(' && arr[i] != ')') || (stack.pop() == '{' && arr[i] != '}') || (stack.pop() == '[' && arr[i] != ']')) {
return false; // here we return false because this tells us that there is a mismatch and not balanced. Also if we did pop out the brace and it was equal
// to it's corresponding closing brace then it will just continue the loop other return false to indicate it is unbalanced.
}
}
}
if(stack.isEmpty()) {
return true; // after looping through the text if the stack turns out to be empty then this shows that there the text is balanced indeed because
}
else {
return false;
}
}
}