Например, если скобки/скобки соответствует по следующим:
({})
(()){}()
()
и так далее, но если скобки/скобки не совпадающие она должна возвращать false, например:
{}
({}(
){})
(()
и так далее. Можете ли вы проверить этот код? Спасибо заранее.
в
public static boolean isParenthesisMatch(String str) {
Stack<Character> stack = new Stack<Character>();
char c;
for(int i=0; i < str.length(); i++) {
c = str.charAt(i);
if(c == '{')
return false;
if(c == '(')
stack.push(c);
if(c == '{') {
stack.push(c);
if(c == '}')
if(stack.empty())
return false;
else if(stack.peek() == '{')
stack.pop();
}
else if(c == ')')
if(stack.empty())
return false;
else if(stack.peek() == '(')
stack.pop();
else
return false;
}
return stack.empty();
}
public static void main(String[] args) {
String str = "({})";
System.out.println(Weekly12.parenthesisOtherMatching(str));
}
Ваш код имеет некоторую сумятицу в ее обработки '{' и '}' символы. Оно должно быть совершенно параллельно, как вы справляетесь с '(' и ')'.
Этот код, немного измененный от вашего, кажется, чтобы работать должным образом:
public static boolean isParenthesisMatch(String str) {
if (str.charAt(0) == '{')
return false;
Stack<Character> stack = new Stack<Character>();
char c;
for(int i=0; i < str.length(); i++) {
c = str.charAt(i);
if(c == '(')
stack.push(c);
else if(c == '{')
stack.push(c);
else if(c == ')')
if(stack.empty())
return false;
else if(stack.peek() == '(')
stack.pop();
else
return false;
else if(c == '}')
if(stack.empty())
return false;
else if(stack.peek() == '{')
stack.pop();
else
return false;
}
return stack.empty();
}
Этот код проще для понимания:
public static boolean CheckParentesis(String str)
{
if (str.isEmpty())
return true;
Stack<Character> stack = new Stack<Character>();
for (int i = 0; i < str.length(); i++)
{
char current = str.charAt(i);
if (current == '{' || current == '(' || current == '[')
{
stack.push(current);
}
if (current == '}' || current == ')' || current == ']')
{
if (stack.isEmpty())
return false;
char last = stack.peek();
if (current == '}' && last == '{' || current == ')' && last == '(' || current == ']' && last == '[')
stack.pop();
else
return false;
}
}
return stack.isEmpty();
}
Алгоритм:
Теперь, скобки сбалансированы для двух условий:
public static boolean isValidExpression(String expression) {
Map<Character, Character> openClosePair = new HashMap<Character, Character>();
openClosePair.put(')', '(');
openClosePair.put('}', '{');
openClosePair.put(']', '[');
Stack<Character> stack = new Stack<Character>();
for(char ch : expression.toCharArray()) {
if(openClosePair.containsKey(ch)) {
if(stack.pop() != openClosePair.get(ch)) {
return false;
}
} else if(openClosePair.values().contains(ch)) {
stack.push(ch);
}
}
return stack.isEmpty();
}
На самом деле, нет необходимости для проверки любых случаях"на глаз" вручную&;. Вы можете просто выполнить следующий алгоритм:
Перебора заданной последовательности. Начните с пустого стека.
Если текущий символ является открывающей скобкой, просто толкать его в стек.
Если это'с закрывающей скобкой, проверить, что стек не пуст и верхний элемент шаг является соответствующая открывающая скобка(то есть, совпадает с вашей). Если это не так, сообщить об ошибке. В противном случае, извлекает верхний элемент из стека.
В конце концов, эта последовательность правильным, если стек пуст.
Почему это правильно? Вот набросок доказательства: если этот алгоритм сообщили, что последовательность будет исправлена, он нашел подходящую пару все скобки. Таким образом, последовательность-это действительно правильно по определению. Если он сообщил об ошибке:
Если стек не пуст, в конце концов, баланс открывающих и закрывающих скобок не равна нулю. Таким образом, это не правильная последовательность.
Если стек был пуст, когда мы должны были поп-элемент, баланс снова.
Если бы был неправильный элемент на вершине стека, пара на "неправильную" в скобках должны соответствовать друг другу. Это означает, что последовательность не правильная.
Я показал, что:
Если алгоритм сообщила, что последовательность правильная, это правильно.
Если алгоритм сообщила, что последовательность не правильная, это некорректно(обратите внимание, что я не пользуюсь тем, что нет никаких других дел, кроме тех, что упомянули в своем вопросе).
Эти два пункта означают, что этот алгоритм работает для всех возможных входов.
public static boolean isBalanced(String s) {
Map<Character, Character> openClosePair = new HashMap<Character, Character>();
openClosePair.put('(', ')');
openClosePair.put('{', '}');
openClosePair.put('[', ']');
Stack<Character> stack = new Stack<Character>();
for (int i = 0; i < s.length(); i++) {
if (openClosePair.containsKey(s.charAt(i))) {
stack.push(s.charAt(i));
} else if ( openClosePair.containsValue(s.charAt(i))) {
if (stack.isEmpty())
return false;
if (openClosePair.get(stack.pop()) != s.charAt(i))
return false;
}
// ignore all other characters
}
return stack.isEmpty();
}
Вы're делая некоторые дополнительные проверки, которые арен'т нужна. Не'т делать какие-либо различия в функциональности, но более рациональный способ, чтобы написать код будет такой:
public static boolean isParenthesisMatch(String str) {
Stack<Character> stack = new Stack<Character>();
char c;
for (int i = 0; i < str.length(); i++) {
c = str.charAt(i);
if (c == '(' || c == '{')
stack.push(c);
else if (stack.empty())
return false;
else if (c == ')') {
if (stack.pop() != '(')
return false;
} else if (c == '}') {
if (stack.pop() != '{')
return false;
}
}
return stack.empty();
}
Нет никаких причин, чтобы взглянуть на paranthesis перед извлечением его из стека. Я'd также оборачивать инструкция блоков в parantheses для улучшения читабельности.
Оптимизированная реализация с помощью стеки и переключатель заявление:
public class JavaStack {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
Stack<Character> s = new Stack<Character>();
while (sc.hasNext()) {
String input = sc.next();
for (int i = 0; i < input.length(); i++) {
char c = input.charAt(i);
switch (c) {
case '(':
s.push(c); break;
case '[':
s.push(c); break;
case '{':
s.push(c); break;
case ')':
if (!s.isEmpty() && s.peek().equals('(')) {
s.pop();
} else {
s.push(c);
} break;
case ']':
if (!s.isEmpty() && s.peek().equals('[')) {
s.pop();
} else {
s.push(c);
} break;
case '}':
if (!s.isEmpty() && s.peek().equals('{')) {
s.pop();
} else {
s.push(c);
} break;
default:
s.push('x'); break;
}
}
if (s.empty()) {
System.out.println("true");
} else {
System.out.println("false");
s.clear();
}
}
} }
Ура !
Ганесан's выше ответ не верный и StackOverflow не позволил мне комментировать или редактировать свой пост. Поэтому ниже приводится правильный ответ. Ганесан имеет неправильную видом на "[" и отсутствует пустой стек() проверить.
Приведенный ниже код будет возвращать true, если брекеты правильно подобранный.
public static boolean isValidExpression(String expression) {
Map<Character, Character> openClosePair = new HashMap<Character, Character>();
openClosePair.put(')', '(');
openClosePair.put('}', '{');
openClosePair.put(']', '[');
Stack<Character> stack = new Stack<Character>();
for(char ch : expression.toCharArray()) {
if(openClosePair.containsKey(ch)) {
if(stack.isEmpty() || stack.pop() != openClosePair.get(ch)) {
return false;
}
} else if(openClosePair.values().contains(ch)) {
stack.push(ch);
}
}
return stack.isEmpty();
}
Алгоритм составляет:
1)Create a stack
2)while(end of input is not reached)
i)if the character read is not a sysmbol to be balanced ,ignore it.
ii)if the character is {,[,( then push it to stack
iii)If it is a },),] then if
a)the stack is empty report an error(catch it) i.e not balanced
b)else pop the stack
iv)if element popped is not corresponding to opening sysmbol,then report error.
3) In the end,if stack is not empty report error else expression is balanced.
В Java-код:
public class StackDemo {
public static void main(String[] args) throws Exception {
System.out.println("--Bracket checker--");
CharStackArray stack = new CharStackArray(10);
stack.balanceSymbol("[a+b{c+(e-f[p-q])}]") ;
stack.display();
}
}
class CharStackArray {
private char[] array;
private int top;
private int capacity;
public CharStackArray(int cap) {
capacity = cap;
array = new char[capacity];
top = -1;
}
public void push(char data) {
array[++top] = data;
}
public char pop() {
return array[top--];
}
public void display() {
for (int i = 0; i <= top; i++) {
System.out.print(array[i] + "->");
}
}
public char peek() throws Exception {
return array[top];
}
/*Call this method by passing a string expression*/
public void balanceSymbol(String str) {
try {
char[] arr = str.toCharArray();
for (int i = 0; i < arr.length; i++) {
if (arr[i] == '[' || arr[i] == '{' || arr[i] == '(')
push(arr[i]);
else if (arr[i] == '}' && peek() == '{')
pop();
else if (arr[i] == ']' && peek() == '[')
pop();
else if (arr[i] == ')' && peek() == '(')
pop();
}
if (isEmpty()) {
System.out.println("String is balanced");
} else {
System.out.println("String is not balanced");
}
} catch (Exception e) {
System.out.println("String not balanced");
}
}
public boolean isEmpty() {
return (top == -1);
}
}
Выход:
--Проверки--кронштейн
Строка является сбалансированным
Я думаю, это лучший ответ:
public boolean isValid(String s) {
Map<Character, Character> map = new HashMap<>();
map.put('(', ')');
map.put('[', ']');
map.put('{', '}');
Stack<Character> stack = new Stack<>();
for(char c : s.toCharArray()){
if(map.containsKey(c)){
stack.push(c);
} else if(!stack.empty() && map.get(stack.peek())==c){
stack.pop();
} else {
return false;
}
}
return stack.empty();
}
import java.util.*;
class StackDemo {
public static void main(String[] argh) {
boolean flag = true;
String str = "(()){}()";
int l = str.length();
flag = true;
Stack<String> st = new Stack<String>();
for (int i = 0; i < l; i++) {
String test = str.substring(i, i + 1);
if (test.equals("(")) {
st.push(test);
} else if (test.equals("{")) {
st.push(test);
} else if (test.equals("[")) {
st.push(test);
} else if (test.equals(")")) {
if (st.empty()) {
flag = false;
break;
}
if (st.peek().equals("(")) {
st.pop();
} else {
flag = false;
break;
}
} else if (test.equals("}")) {
if (st.empty()) {
flag = false;
break;
}
if (st.peek().equals("{")) {
st.pop();
} else {
flag = false;
break;
}
} else if (test.equals("]")) {
if (st.empty()) {
flag = false;
break;
}
if (st.peek().equals("[")) {
st.pop();
} else {
flag = false;
break;
}
}
}
if (flag && st.empty())
System.out.println("true");
else
System.out.println("false");
}
}
Я видел тут ответы и почти все сделали хорошо. Однако, я написал свою версию, которая использует словарь для управления парами кронштейн и стек для отслеживания заказа обнаруженных брекеты. Я также написал в блоге пост для этого.
Вот мой класс
public class FormulaValidator
{
// Question: Check if a string is balanced. Every opening bracket is matched by a closing bracket in a correct position.
// { [ ( } ] )
// Example: "()" is balanced
// Example: "{ ]" is not balanced.
// Examples: "()[]{}" is balanced.
// "{([])}" is balanced
// "{ ( [ ) ] }" is _not_ balanced
// Input: string, containing the bracket symbols only
// Output: true or false
public bool IsBalanced(string input)
{
var brackets = BuildBracketMap();
var openingBraces = new Stack<char>();
var inputCharacters = input.ToCharArray();
foreach (char character in inputCharacters)
{
if (brackets.ContainsKey(character))
{
openingBraces.Push(character);
}
if (brackets.ContainsValue(character))
{
var closingBracket = character;
var openingBracket = brackets.FirstOrDefault(x => x.Value == closingBracket).Key;
if (openingBraces.Peek() == openingBracket)
openingBraces.Pop();
else
return false;
}
}
return openingBraces.Count == 0;
}
private Dictionary<char, char> BuildBracketMap()
{
return new Dictionary<char, char>()
{
{'[', ']'},
{'(', ')'},
{'{', '}'}
};
}
}
//basic code non strack algorithm just started learning java ignore space and time.
/// {[()]}[][]{}
// {[( -a -> }]) -b -> replace a(]}) -> reverse a( }]))->
//Split string to substring {[()]}, next [], next [], next{}
public class testbrackets {
static String stringfirst;
static String stringsecond;
static int open = 0;
public static void main(String[] args) {
splitstring("(()){}()");
}
static void splitstring(String str){
int len = str.length();
for(int i=0;i<=len-1;i++){
stringfirst="";
stringsecond="";
System.out.println("loop starttttttt");
char a = str.charAt(i);
if(a=='{'||a=='['||a=='(')
{
open = open+1;
continue;
}
if(a=='}'||a==']'||a==')'){
if(open==0){
System.out.println(open+"started with closing brace");
return;
}
String stringfirst=str.substring(i-open, i);
System.out.println("stringfirst"+stringfirst);
String stringsecond=str.substring(i, i+open);
System.out.println("stringsecond"+stringsecond);
replace(stringfirst, stringsecond);
}
i=(i+open)-1;
open=0;
System.out.println(i);
}
}
static void replace(String stringfirst, String stringsecond){
stringfirst = stringfirst.replace('{', '}');
stringfirst = stringfirst.replace('(', ')');
stringfirst = stringfirst.replace('[', ']');
StringBuilder stringfirst1 = new StringBuilder(stringfirst);
stringfirst = stringfirst1.reverse().toString();
System.out.println("stringfirst"+stringfirst);
System.out.println("stringsecond"+stringsecond);
if(stringfirst.equals(stringsecond)){
System.out.println("pass");
}
else{
System.out.println("fail");
System.exit(0);
}
}
}
Я попытался это с помощью JavaScript ниже результат.
function bracesChecker(str) {
if(!str) {
return true;
}
var openingBraces = ['{', '[', '('];
var closingBraces = ['}', ']', ')'];
var stack = [];
var openIndex;
var closeIndex;
//check for opening Braces in the val
for (var i = 0, len = str.length; i < len; i++) {
openIndex = openingBraces.indexOf(str[i]);
closeIndex = closingBraces.indexOf(str[i]);
if(openIndex !== -1) {
stack.push(str[i]);
}
if(closeIndex !== -1) {
if(openingBraces[closeIndex] === stack[stack.length-1]) {
stack.pop();
} else {
return false;
}
}
}
if(stack.length === 0) {
return true;
} else {
return false;
}
}
var testStrings = [
'',
'test',
'{{[][]()()}()}[]()',
'{test{[test]}}',
'{test{[test]}',
'{test{(yo)[test]}}',
'test{[test]}}',
'te()s[]t{[test]}',
'te()s[]t{[test'
];
testStrings.forEach(val => console.log(`${val} => ${bracesChecker(val)}`));
Если вы хотите взглянуть на мой код. Просто для справки
public class Default {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int numOfString = Integer.parseInt(br.readLine());
String s;
String stringBalanced = "YES";
Stack<Character> exprStack = new Stack<Character>();
while ((s = br.readLine()) != null) {
stringBalanced = "YES";
int length = s.length() - 1;
for (int i = 0; i <= length; i++) {
char tmp = s.charAt(i);
if(tmp=='[' || tmp=='{' || tmp=='('){
exprStack.push(tmp);
}else if(tmp==']' || tmp=='}' || tmp==')'){
if(!exprStack.isEmpty()){
char peekElement = exprStack.peek();
exprStack.pop();
if(tmp==']' && peekElement!='['){
stringBalanced="NO";
}else if(tmp=='}' && peekElement!='{'){
stringBalanced="NO";
}else if(tmp==')' && peekElement!='('){
stringBalanced="NO";
}
}else{
stringBalanced="NO";
break;
}
}
}
if(!exprStack.isEmpty()){
stringBalanced = "NO";
}
exprStack.clear();
System.out.println(stringBalanced);
}
}
}
public static bool IsBalanced(string input)
{
Dictionary<char, char> bracketPairs = new Dictionary<char, char>() {
{ '(', ')' },
{ '{', '}' },
{ '[', ']' },
{ '<', '>' }
};
Stack<char> brackets = new Stack<char>();
try
{
// Iterate through each character in the input string
foreach (char c in input)
{
// check if the character is one of the 'opening' brackets
if (bracketPairs.Keys.Contains(c))
{
// if yes, push to stack
brackets.Push(c);
}
else
// check if the character is one of the 'closing' brackets
if (bracketPairs.Values.Contains(c))
{
// check if the closing bracket matches the 'latest' 'opening' bracket
if (c == bracketPairs[brackets.First()])
{
brackets.Pop();
}
else
// if not, its an unbalanced string
return false;
}
else
// continue looking
continue;
}
}
catch
{
// an exception will be caught in case a closing bracket is found,
// before any opening bracket.
// that implies, the string is not balanced. Return false
return false;
}
// Ensure all brackets are closed
return brackets.Count() == 0 ? true : false;
}
public String checkString(String value) {
Stack<Character> stack = new Stack<>();
char topStackChar = 0;
for (int i = 0; i < value.length(); i++) {
if (!stack.isEmpty()) {
topStackChar = stack.peek();
}
stack.push(value.charAt(i));
if (!stack.isEmpty() && stack.size() > 1) {
if ((topStackChar == '[' && stack.peek() == ']') ||
(topStackChar == '{' && stack.peek() == '}') ||
(topStackChar == '(' && stack.peek() == ')')) {
stack.pop();
stack.pop();
}
}
}
return stack.isEmpty() ? "YES" : "NO";
}
Здесь'ы решение в Python.
#!/usr/bin/env python
def brackets_match(brackets):
stack = []
for char in brackets:
if char == "{" or char == "(" or char == "[":
stack.append(char)
if char == "}":
if stack[-1] == "{":
stack.pop()
else:
return False
elif char == "]":
if stack[-1] == "[":
stack.pop()
else:
return False
elif char == ")":
if stack[-1] == "(":
stack.pop()
else:
return False
if len(stack) == 0:
return True
else:
return False
if __name__ == "__main__":
print(brackets_match("This is testing {([])} if brackets have match."))
Было предложено реализовать этот алгоритм в интервью в прямом эфире кодирования, здесь's мой рефакторинг решение на C#: