【九度】题目1153：括号匹配问题

本文主要是介绍【九度】题目1153：括号匹配问题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目地址：http://ac.jobdu.com/problem.php?pid=1153
题目描述：

    在某个字符串（长度不超过100）中有左括号、右括号和大小写字母；规定（与常见的算数式子一样）任何一个左括号都从内到外与在它右边且距离最近的右括号匹配。写一个程序，找到无法匹配的左括号和右括号，输出原来字符串，并在下一行标出不能匹配的括号。不能匹配的左括号用"$"标注,不能匹配的右括号用"?"标注.

输入：

    输入包括多组数据，每组数据一行，包含一个字符串，只包含左右括号和大小写字母，字符串长度不超过100。
    注意：cin.getline(str,100)最多只能输入99个字符！

输出：

    对每组输出数据，输出两行，第一行包含原始输入字符，第二行由"$","?"和空格组成，"$"和"?"表示与之对应的左括号和右括号不能匹配。

样例输入：

)(rttyy())sss)(

样例输出：

)(rttyy())sss)(
?            ?$

来源：

2010年北京大学计算机研究生机试真题

1153和1337其实思路一样，遇到左括号入栈，遇到右括号，发现栈不为空，出栈，同时将当前位状态改为1。
代码有注释。

C++ AC

#include <stdio.h>
#include <stack>
#include <string>
#include <string.h>
using namespace std;
const int maxn = 102;
char input[maxn];
int main(){int n,i;while(scanf("%s",input) != EOF){stack<int> symStack;n = strlen(input);int *flagArr = new int[n];memset(flagArr,0,sizeof(flagArr));for(i = 0 ; i < n; i++){//如果是左括号，将当前数字入栈，表明位置if(input[i] == '('){symStack.push(i);}else if(input[i] == ')'  && !symStack.empty()){//如果是右括号，并且当前栈不为空，就出栈，同时将位置标为1。//表明有左右括号相匹配。int j = symStack.top();symStack.pop();flagArr[i] = 1;flagArr[j] = 1;}}printf("%s\n",input);//循环输出结果for (i = 0; i < n; i++) {if (input[i] == '(') {//发现是左括号，并且标志位为1，表示有右括号匹配，输出空格。if(flagArr[i] != 1){printf("$");}else{//否则输出$printf(" ");}}else if (input[i] == ')') {//发现是右括号，并且标志位为1，表示有左括号匹配，输出空格。if(flagArr[i] != 1){printf("?");}else{//否则输出?printf(" ");}}else{printf(" ");}}printf("\n");}return 0;
} 
/**************************************************************Problem: 1153User: wangzhenqingLanguage: C++Result: AcceptedTime:0 msMemory:1052 kb
****************************************************************/

Java AC 

import java.util.Scanner;
import java.util.Stack;public class Main{/** 1153*/public static void main(String[] args) throws  Exception {Scanner scanner = new Scanner(System.in);while (scanner.hasNextLine()) {Stack<Character> stack = new Stack<Character>();String a = scanner.nextLine();char array[] = a.toCharArray();int len = array.length;String result[] = new String[len];
//          将括号入栈，主要是左括号。如果发现左括号，就入栈。如果发现右括号，
//          并且栈不为空，那么肯定有坐括号对应，出栈。如果栈空，那么只有右
//          括号，即为不匹配，输出？号。int i = 0;while ( i < len) {if (array[i] == '(') {stack.push(array[i]);result[i] = " ";}else if (array[i] == ')') {if (!stack.isEmpty()) {stack.pop();result[i] = " ";}else {result[i] = "?";}}else {result[i] = " ";}i++;}i = len - 1;int j = 0;while (!stack.isEmpty()) {if (array[i] == ')') {j++;}else if (array[i] == '(') {if (j == 0){result[i] = "$";stack.pop();}else{j--;}}i--;}StringBuffer sb = new StringBuffer();sb.append(a+"\n");for (int k = 0; k < len; k++) {sb.append(result[k]);}System.out.println(sb.toString());}}
}
/**************************************************************Problem: 1153User: wzqwsrfLanguage: JavaResult: AcceptedTime:80 msMemory:15464 kb
****************************************************************/

这篇关于【九度】题目1153：括号匹配问题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---