用C语言解决此题:括弧匹配问题:编写程序,从标准输入得到的一个缺失左括号的表达式,输出补全括号之后的中序表达式。例如:输入1+2)*3-4)*5-6)));则程序应该输出((1+2)*((3-4)*(5-6)))
时间: 2024-10-21 22:05:52 浏览: 40
在C语言中,解决括号匹配问题可以采用栈的数据结构,因为括号的匹配遵循“入栈”对应“出栈”的规则。下面是一个简单的解决方案:
```c
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
bool is_valid(char* exp) {
int stack[100], top = -1;
for (int i = 0; exp[i] != '\0'; ++i) {
if (exp[i] == '(')
stack[++top] = '(';
else if (exp[i] == ')') {
if (top == -1 || stack[top] != '(')
return false;
stack[top--] = ')';
}
}
return top == -1;
}
char* fill_parens(char* input) {
char* result = malloc(strlen(input) * 2 + 2);
if (!result)
return NULL;
bool in_quotes = false;
int left_brackets = 0;
int start_index = 0;
int result_idx = 0;
for (int i = 0; input[i]; ++i) {
if (input[i] == '"' && !in_quotes) {
in_quotes = true;
continue;
}
if (input[i] == '"' && in_quotes) {
in_quotes = false;
input[i] = '\0';
result[result_idx++] = '"';
}
if (!in_quotes && input[i] == '(') {
left_brackets++;
if (!left_brackets)
start_index = i;
} else if (!in_quotes && input[i] == ')' && left_brackets > 0) {
left_brackets--;
if (left_brackets == 0) {
result[result_idx++] = '(';
result[result_idx++] = ')';
while (start_index < i) {
result[result_idx++] = input[start_index];
start_index++;
}
}
}
result[result_idx++] = input[i];
}
if (left_brackets > 0)
return NULL; // 表达式不合法,有未关闭的括号
result[result_idx] = '\0';
return result;
}
int main() {
char input[] = "1+2)*3-4)*5-6)))";
char* completed_expr = fill_parens(input);
if (completed_expr) {
printf("Output: %s\n", completed_expr);
free(completed_expr); // 释放内存
} else {
printf("Invalid expression.\n");
}
return 0;
}
```
这个程序首先检查原始表达式的括号是否闭合,如果不闭合则进行填充。`fill_parens`函数遍历输入字符串,遇到每个字符时判断其是否需要添加一对括号。如果检测到不平衡的括号,返回NULL表示无法完成。
运行上述代码,将得到补全后的中序表达式。
阅读全文