括号匹配

秒速五厘米 2022-06-02 08:53 253阅读 0赞

4 括号匹配 （10分）

成绩: 10 / 折扣: 0.8

假设一个算术表达式中包含圆括号、方括号两种类型的括号，试编写一个判断表达式中括号是否匹配的程序，匹配返回Match succeed!，否则返回Match false!。

例

\[1+2\*(3+4\*(5+6))\]括号匹配

(1+2)\*(1+2\*\[(1+2)+3)括号不匹配

## 输入 ##

包含圆括号、方括号两种类型括号的算术表达式

## 输出 ##

匹配输出Match succeed!

不匹配输出 Match false!

例

输入\[1+2\* (3+4\*(5+6))\]

输出Match succeed!

<table style="width:1615px; margin-bottom:20px; background-color:transparent"> 
 <thead> 
  <tr> 
   <th style="padding:4px; line-height:20px; vertical-align:bottom; border-top-width:0px"> &nbsp;</th> 
   <th style="padding:4px; line-height:20px; vertical-align:bottom; border-top-width:0px"> 测试输入<span><a href="http://online.bit.edu.cn/moodle/help.php?component=programming&amp;identifier=input&amp;lang=zh_cn" title="关于“测试输入”的帮助" style="color:rgb(67,142,185)" rel="nofollow"><img src="http://online.bit.edu.cn/moodle/theme/image.php/lambda/core/1510491239/help" alt="关于“测试输入”的帮助" style="vertical-align:text-bottom; border:0px; height:16px; padding-left:3px; width:16px"></a></span></th> 
   <th style="padding:4px; line-height:20px; vertical-align:bottom; border-top-width:0px"> 期待的输出<span><a href="http://online.bit.edu.cn/moodle/help.php?component=programming&amp;identifier=expectedoutput&amp;lang=zh_cn" title="关于“期待的输出”的帮助" style="color:rgb(67,142,185)" rel="nofollow"><img src="http://online.bit.edu.cn/moodle/theme/image.php/lambda/core/1510491239/help" alt="关于“期待的输出”的帮助" style="vertical-align:text-bottom; border:0px; height:16px; padding-left:3px; width:16px"></a></span></th> 
   <th style="padding:4px; line-height:20px; vertical-align:bottom; border-top-width:0px"> 时间限制<span><a href="http://online.bit.edu.cn/moodle/help.php?component=programming&amp;identifier=timelimit&amp;lang=zh_cn" title="关于“时间限制”的帮助" style="color:rgb(67,142,185)" rel="nofollow"><img src="http://online.bit.edu.cn/moodle/theme/image.php/lambda/core/1510491239/help" alt="关于“时间限制”的帮助" style="vertical-align:text-bottom; border:0px; height:16px; padding-left:3px; width:16px"></a></span></th> 
   <th style="padding:4px; line-height:20px; vertical-align:bottom; border-top-width:0px"> 内存限制<span><a href="http://online.bit.edu.cn/moodle/help.php?component=programming&amp;identifier=memlimit&amp;lang=zh_cn" title="关于“内存限制”的帮助" style="color:rgb(67,142,185)" rel="nofollow"><img src="http://online.bit.edu.cn/moodle/theme/image.php/lambda/core/1510491239/help" alt="关于“内存限制”的帮助" style="vertical-align:text-bottom; border:0px; height:16px; padding-left:3px; width:16px"></a></span></th> 
   <th style="padding:4px; line-height:20px; vertical-align:bottom; border-top-width:0px"> 额外进程<span><a href="http://online.bit.edu.cn/moodle/help.php?component=programming&amp;identifier=nproc&amp;lang=zh_cn" title="关于“{$a} 个额外进程”的帮助" style="color:rgb(67,142,185)" rel="nofollow"><img src="http://online.bit.edu.cn/moodle/theme/image.php/lambda/core/1510491239/help" alt="关于“{$a} 个额外进程”的帮助" style="vertical-align:text-bottom; border:0px; height:16px; padding-left:3px; width:16px"></a></span></th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td style="padding:4px; line-height:20px; vertical-align:middle; background-color:rgb(249,249,249)"> 测试用例 1</td> 
   <td style="padding:4px; line-height:20px; vertical-align:middle; background-color:rgb(249,249,249)"> <a href="http://online.bit.edu.cn/moodle/mod/programming/testcase/download_io.php?id=64761&amp;test=82470&amp;type=in&amp;download=0" style="color:rgb(67,142,185); font-size:9pt" rel="nofollow">以文本方式显示</a> 
    <div style="vertical-align:top; padding:0px 5px 0px 0px; width:10em; height:10em; overflow:auto"> 
     <ol style="padding-left:0px; margin-bottom:0px; margin-left:2.5em; overflow:visible"> 
      <li style="line-height:20px; font-family:Consolas,'Courier New',Courier,mono,serif; margin:0px; padding:0px; overflow:visible"> <span style="margin:0px; padding:0px; white-space:nowrap; background-color:rgb(211,211,211)">[1+2*(3+4*(5+6))]↵</span></li> 
     </ol> 
    </div> </td> 
   <td style="padding:4px; line-height:20px; vertical-align:middle; background-color:rgb(249,249,249)"> <a href="http://online.bit.edu.cn/moodle/mod/programming/testcase/download_io.php?id=64761&amp;test=82470&amp;type=out&amp;download=0" style="color:rgb(67,142,185); font-size:9pt" rel="nofollow">以文本方式显示</a> 
    <div style="vertical-align:top; padding:0px 5px 0px 0px; width:10em; height:10em; overflow:auto"> 
     <ol style="padding-left:0px; margin-bottom:0px; margin-left:2.5em; overflow:visible"> 
      <li style="line-height:20px; font-family:Consolas,'Courier New',Courier,mono,serif; margin:0px; padding:0px; overflow:visible"> <span style="margin:0px; padding:0px; white-space:nowrap; background-color:rgb(211,211,211)">Match&nbsp;succeed!↵</span></li> 
     </ol> 
    </div> </td> 
   <td style="padding:4px; line-height:20px; vertical-align:middle; background-color:rgb(249,249,249)"> 1秒</td> 
   <td style="padding:4px; line-height:20px; vertical-align:middle; background-color:rgb(249,249,249)"> 64M</td> 
   <td style="padding:4px; line-height:20px; vertical-align:middle; background-color:rgb(249,249,249)"> 0</td> 
  </tr> 
  <tr> 
   <td style="padding:4px; line-height:20px; vertical-align:middle"> 测试用例 2</td> 
   <td style="padding:4px; line-height:20px; vertical-align:middle"> <a href="http://online.bit.edu.cn/moodle/mod/programming/testcase/download_io.php?id=64761&amp;test=82471&amp;type=in&amp;download=0" style="color:rgb(67,142,185); font-size:9pt" rel="nofollow">以文本方式显示</a> 
    <div style="vertical-align:top; padding:0px 5px 0px 0px; width:10em; height:10em; overflow:auto"> 
     <ol style="padding-left:0px; margin-bottom:0px; margin-left:2.5em; overflow:visible"> 
      <li style="line-height:20px; font-family:Consolas,'Courier New',Courier,mono,serif; margin:0px; padding:0px; overflow:visible"> <span style="margin:0px; padding:0px; white-space:nowrap; background-color:rgb(211,211,211)">(1+2)*(1+2*[(1+2)+3)↵</span></li> 
     </ol> 
    </div> </td> 
   <td style="padding:4px; line-height:20px; vertical-align:middle"> <a href="http://online.bit.edu.cn/moodle/mod/programming/testcase/download_io.php?id=64761&amp;test=82471&amp;type=out&amp;download=0" style="color:rgb(67,142,185); font-size:9pt" rel="nofollow">以文本方式显示</a> 
    <div style="vertical-align:top; padding:0px 5px 0px 0px; width:10em; height:10em; overflow:auto"> 
     <ol style="padding-left:0px; margin-bottom:0px; margin-left:2.5em; overflow:visible"> 
      <li style="line-height:20px; font-family:Consolas,'Courier New',Courier,mono,serif; margin:0px; padding:0px; overflow:visible"> <span style="margin:0px; padding:0px; white-space:nowrap; background-color:rgb(211,211,211)">Match&nbsp;false!↵</span></li> 
     </ol> 
    </div> </td> 
   <td style="padding:4px; line-height:20px; vertical-align:middle"> 1秒</td> 
   <td style="padding:4px; line-height:20px; vertical-align:middle"> 64M</td> 
   <td style="padding:4px; line-height:20px; vertical-align:middle"> 0<br> </td> 
  </tr> 
 </tbody> 
</table>

#include<cstdio> 
    #include<string> 
    #include<map> 
    #include<stack> 
    #include<math.h> 
    #include<iostream> 
    using namespace std; 
    stack<char> Op; 
    stack<int>  Opnum; 
    string Instruction; 
    string tmp; 
    int main() 
    { 
       //freopen("1.txt", "r", stdin); 
        int flag1 = 1; 
     int Bleft = 0, Bright = 0, Sleft = 0, Sright = 0; 
      getline(cin, Instruction); 
     for (int i = 0; Instruction[i]; i++) 
       { 
          if (Instruction[i] != '('&& Instruction[i] != ')' && Instruction[i] != '[' && Instruction[i] != ']') 
               continue; 
          else 
           { 
              if (Op.empty() || Instruction[i] == '(' || Instruction[i] == '[') 
              { 
                  if (Instruction[i] == ']' || Instruction[i] == ')') 
                    { 
                      flag1 = 0; 
                     break; 
                 } 
                  else if (Instruction[i] == '(') 
                        Sleft++; 
                   else if (Instruction[i] == '[') 
                        Bleft++; 
                   Op.push(Instruction[i]); 
               } 
              else if (Instruction[i] == ')') 
                { 
                  Sright++; 
                  if (Sright > Sleft) 
                 { 
                      flag1 = 0; 
                     break; 
                 } 
                  char op; 
                   while (!Op.empty() && (op = Op.top()) != '(') 
                  { 
                      if (op == '[') 
                     { 
                          flag1 = 0; 
                         break; 
                     } 
                      Op.pop(); 
                  } 
                  if (!flag1) 
                        break; 
                 Op.pop(); 
              } 
              else if (Instruction[i] == ']') 
                { 
                  Bright++; 
                  if (Bright > Bleft) 
                 { 
                      flag1 = 0; break; 
                  } 
                  char op; 
                   while (!Op.empty()&&(op=Op.top())!='[') 
                    { 
                      Op.pop(); 
                  } 
                  Op.pop(); 
              } 
          } 
      } 
      if (!Op.empty()) flag1 = 0; 
        if (!flag1) 
            printf("Match false!\n"); 
      else 
           printf("Match succeed!\n"); 
        return 0; 
    }