在過去的兩個小時里，我一直在嘗試除錯我的代碼，該代碼應該檢查輸入是否包含格式正確的括號。我所說的格式良好的意思是()()[]可以([()])接受，但((((()不是。
我不允許使用任何頭檔案除了<stdio.h>
#include <stdio.h>
void cross(char str[], int i, int j) {
str[i] = 'X';
str[j] = 'X';
}
int iscrossed(char str[]) {
int i = 0;
while (str[i] != '\0') {
if (str[i] != 'X')
return 0;
i ;
}
return 1;
}
int check(char str[]) {
int i = 1, j;
while (str[i] != '\0') {
if (str[i] == ')') {
for (j = i - 1; j >= 0; j--) {
if (str[j] == '(') {
cross(str, str[i], str[j]);
}
break;
}
} else
if (str[i] == ']') {
for (j = i - 1; j >= 0; j--) {
if (str[j] == '[') {
cross(str, str[i], str[j]);
}
break;
}
}
i ;
}
if (iscrossed(str) == 1)
return 1;
else
return 0;
}
int main() {
char str[20];
scanf("%s", str);
printf("%d\n", check(str));
}
對于某些輸入，程式會列印一個零，然后是分段錯誤，而對于其他輸入，它只列印一個零。請記住，我是初學者，所以請不要在提示中包含太多繁重的內容。對于這方面的任何幫助，我將不勝感激。
編輯：如果您的回答告訴我代碼中的錯誤，那就太好了，因為這首先是我的問題。
uj5u.com熱心網友回復：
可能答案的偽代碼：
initialize char[] unclosed
int latest_unclosed_index = -1
for each char in string {
if char == opening_bracket {
latest_unclosed_index = 1
unclosed[latest_unclosed_index] = char
} else if char == closing_bracket {
if latest_unclosed_index < 0 {
return false
} else if char == closing_of(unclosed[latest_unclosed_index]) {
unclosed[latest_unclosed_index] = null
latest_unclosed_index -= 1
} else {
return false
}
}
}
if latest_unclosed_index == -1 {
return true
} else {
return false
}
這是通過按照您遇到它們的順序保留所有未閉合的左括號的陣列，并在遇到右括號時將它們洗掉，作為一種堆疊。
該解決方案的復雜度為 O(n)。
這個實作的一個問題是字串中存在未知數量的括號，如果它不夠大，可能會導致陣列溢位。
解決方案：
- 為確保此解決方案不會溢位，陣列的大小應至少為輸入字串大小的一半，并且您必須檢查每個字符是否有足夠的字符留在輸入字串中能夠完全關閉所有括號。
- 使用串列實作（或自己撰寫）而不是陣列
unclosed。
uj5u.com熱心網友回復：
這是一個簡單的遞回解決方案：
#include <stdio.h>
int brace(const char **s, char cc)
{
while(1) {
if(**s == cc) { return 0; }
switch(**s) {
case '\0': return -1;
case '[': (*s); if(brace(s, ']')) { return -1; } (*s); break;
case '{': (*s); if(brace(s, '}')) { return -1; } (*s); break;
case '(': (*s); if(brace(s, ')')) { return -1; } (*s); break;
case ']':
case '}':
case ')': return -1;
default: (*s);
}
}
}
int check_brace(const char *s)
{
return brace(&s, '\0');
}
int main()
{
printf("%d\n", check_brace(" hekl(l o{ asdf } te)ts()({})"));
}
出現問題時回傳-1。否則字串的長度。
uj5u.com熱心網友回復：
如果你可以使用stdlib.h，那么，
#include <stdio.h>
#include <stdlib.h>
#define bool int
// structure of a stack node
struct sNode {
char data;
struct sNode* next;
};
// Function to push an item to stack
void push(struct sNode** top_ref, int new_data);
// Function to pop an item from stack
int pop(struct sNode** top_ref);
// Returns 1 if character1 and character2 are matching left
// and right Brackets
bool isMatchingPair(char character1, char character2)
{
if (character1 == '(' && character2 == ')')
return 1;
else if (character1 == '{' && character2 == '}')
return 1;
else if (character1 == '[' && character2 == ']')
return 1;
else
return 0;
}
// Return 1 if expression has balanced Brackets
bool areBracketsBalanced(char exp[])
{
int i = 0;
// Declare an empty character stack
struct sNode* stack = NULL;
// Traverse the given expression to check matching
// brackets
while (exp[i])
{
// If the exp[i] is a starting bracket then push
// it
if (exp[i] == '{' || exp[i] == '(' || exp[i] == '[')
push(&stack, exp[i]);
// If exp[i] is an ending bracket then pop from
// stack and check if the popped bracket is a
// matching pair*/
if (exp[i] == '}' || exp[i] == ')'
|| exp[i] == ']') {
// If we see an ending bracket without a pair
// then return false
if (stack == NULL)
return 0;
// Pop the top element from stack, if it is not
// a pair bracket of character then there is a
// mismatch.
// his happens for expressions like {(})
else if (!isMatchingPair(pop(&stack), exp[i]))
return 0;
}
i ;
}
// If there is something left in expression then there
// is a starting bracket without a closing
// bracket
if (stack == NULL)
return 1; // balanced
else
return 0; // not balanced
}
// Driver code
int main()
{
char exp[100] = "{()}[]";
// Function call
if (areBracketsBalanced(exp))
printf("Balanced \n");
else
printf("Not Balanced \n");
return 0;
}
// Function to push an item to stack
void push(struct sNode** top_ref, int new_data)
{
// allocate node
struct sNode* new_node
= (struct sNode*)malloc(sizeof(struct sNode));
if (new_node == NULL) {
printf("Stack overflow n");
getchar();
exit(0);
}
// put in the data
new_node->data = new_data;
// link the old list off the new node
new_node->next = (*top_ref);
// move the head to point to the new node
(*top_ref) = new_node;
}
// Function to pop an item from stack
int pop(struct sNode** top_ref)
{
char res;
struct sNode* top;
// If stack is empty then error
if (*top_ref == NULL) {
printf("Stack overflow n");
getchar();
exit(0);
}
else {
top = *top_ref;
res = top->data;
*top_ref = top->next;
free(top);
return res;
}
}
特征
- 支持嵌套的括號，例如
(()) - 支持不良嵌套，例如
([)] - 評論但不是我的評論（見下面的劇透）
注意：我從
像塊代碼一樣的偽代碼！
如果您無法使用
stdlib.h，那么有人可能會編輯此代碼并洗掉我們洗掉該行時發生的錯誤（#include <stdlib.h>），我不是c男人，我不知道編輯，我只是??復制粘貼！uj5u.com熱心網友回復：
正如 MOehm 在評論中所寫的，第一次嘗試不適用于糟糕的嵌套。存盤尚未閉合但已打開的大括號有助于識別錯誤的嵌套。最后打開的大括號將確定需要哪個右大括號。
#include <stdio.h> int check(char str[], int size) { char opened[size/2]; char close; int i = 0; int pos = 0; int error = 0; while((i < size) || (pos < size/2)) { if((str[i] == '(') || (str[i] == '[')) { opened[pos] = str[i]; pos ; } else if((str[i] == ')') || (str[i] == ']')) { if(str[i] == close) { opened[pos-1] = 0; pos--; } else { error = 1; break; } } printf("%s\n", opened); if(pos > 0) { switch(opened[pos-1]) { case '(': close = ')'; break; case '[': close = ']'; break; } } else close = 0; i ; } return error; } int main() { char str[20]; printf("%d\n", check(str, sizeof(str))); return 0; }uj5u.com熱心網友回復：
您的代碼中有多個錯誤：
- 你打電話
cross(str, str[i], str[j]);而不是cross(str, i, j);當你找到括號和括號的匹配項時。- 該
break陳述句應移動到if塊內。- 您的方法不允許檢測嵌套錯誤
str如果是空字串（您不能通過 輸入scanf()） ，您的方法將具有未定義的行為這是修改后的版本：
#include <stdio.h> void cross(char str[], int i, int j) { str[i] = str[j] = 'X'; } int iscrossed(char str[]) { int i = 0; while (str[i] != '\0') { if (str[i] != 'X') return 0; i ; } return 1; } int check(char str[]) { int i = 0, j; while (str[i] != '\0') { if (str[i] == ')') { for (j = i - 1; j >= 0; j--) { if (str[j] == '(') { cross(str, i, j); break; } } } else if (str[i] == ']') { for (j = i - 1; j >= 0; j--) { if (str[j] == '[') { cross(str, i, j); break; } } } i ; } return iscrossed(str); } int main() { char str[80]; if (scanf("ys", str) == 1) { printf("%d\n", check(str)); } return 0; }這是一個更簡單的替代方案：
#include <stdio.h> const char *check(const char str[], int endc) { while (str) { int c = *str ; switch (c) { case '(': str = check(str, ')'); break; case '[': str = check(str, ']'); break; case '{': str = check(str, '}'); break; case ')': case ']': case '}': case '\0': return c == endc ? str : NULL; } } return NULL; } int main() { char str[80]; if (fgets(str, sizeof str, stdin)) { printf("%d\n", check(str, '\0') != NULL); } return 0; }轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/440247.html
標籤：C
上一篇：如何訪問void*字串的i元素？
