本文共 4845 字，大约阅读时间需要 16 分钟。

一、括号匹配问题

1、题目和要求

时间限制：1s，内存限制：32MB，特殊判题：否

2、总结

1）c++有自带的求char数组长度的函数strlen()，头文件是string.h。自己还花时间写了一个函数来求长度。

自己写的函数直接在else里返回 ，但是不符合在线编译器编译规则，应改为下面的写法：在函数末尾return。

//修改前，计算输入字符串长度int stringLength(char* c){
       int i=0;    while(i

2）scanf("%s",input_string)和scanf("%s",&input_string)，第二种写法 ，不符合在线编译器编译规则。数组名本来就表示了数组的首地址，多加一个&，画蛇添足！！！

3）由于系统通过判断是否遇到’\0’，来决定是否终止字符串输出；因此，当数组预留空间大于需要输出的数组长度时，在输出字符串的末尾一定要加上output_string[strlen(input_string)] = '\0'作为结束符，否则还会继续输出一些未知的东西。

---

怎样的char数组，系统会自动在结尾加上’\0’呢？

1.当以字符串形式在代码中为数组赋值时，系统会自动为’\0’开一个存储空间。 2.字符串长度不包括’\0’。

---

3、思路

主要思路：输入字符串后，从后往前遍历。遇到右括号入栈；遇到左括号根据中间栈中的内容进行下一步操作，如果栈为空则不匹配，如果栈顶为右括号则出栈。当输入字符串遍历结束后，若栈中还剩余则不匹配。

4、代码

#include 
   
    #include 
    
     #include 
     
      using namespace std;#define N 100//)(rttyy())sss)(//存储括号和位置信息class bracket{
   private:    int pos;    char value;public:    bracket() {
   };    void set(int p,char v)    {
           pos = p;        value = v;    };    int getPos()    {
           return pos;    }    char getValue()    {
           return value;    }};int main(){
       char input_string[N];           //记录输入字符串    char output_string[N];          //记录输出字符串    int i;                          //记录输入字符串、输出字符串位置    char c;                         //记录当前字符    bracket b;    stack
      
        s;               //中间栈    scanf("%s",input_string);    for(i=strlen(input_string)-1; i>=0; i--)    {
           c = input_string[i];        switch (c)        {
           case ')':            b.set(i,c);            s.push(b);            break;        case '(':            if(s.empty())            {
                   output_string[i] = '$';            }            else            {
                   b = s.top();                if(b.getValue()==')')                {
                       s.pop();                    output_string[i] = ' ';                    output_string[b.getPos()] = ' ';                }            }            break;        default:            output_string[i] = ' ';        }    }    while(!s.empty())    {
           b = s.top();        output_string[b.getPos()] = '?';        s.pop();    }    output_string[strlen(input_string)] = '\0';    printf("%s\n",input_string);    printf("%s\n",output_string);    return 0;}
      
     
    
   

二、简单计算器

1、题目和要求

时间限制：1s，内存限制：32MB，特殊判题：否

2、总结

1）using namespace std和.h两种方式的区别。选自：。

.h是C语言中使用的，当使用.h时，相当于在c中调用库函数，使用的是全局命名空间。 C++ 标准程序库中的所有标识符都被定义于一个名为std的namespace中，因此使用前要声明命名空间。using namespace std是c++中声明命名空间的一种方式。 2）stdio和iostream两种标准输入输出库的区别。 stdio属于c语言，输入输出为printf()，scanf()。 iostream属于c++，输入输出为cout<<…，cin>>…。

3）c++中字符串的存储和读取方式。

在下面的代码中，没有指定getline()函数的结束符，输入ctrl+z即可结束。

4）C语言中保留小数点后两位数：printf("%.2lf",a);

c++中保留小数点后两位数：cout << fixed <<setprecision(2)<<a;

5）注意：

• 操作数出栈顺序与入栈顺序相反，除法和减法操作需注意。
• 进行 “一次” 运算要出栈 “两个操作数” 和 “一个运算符” 。
• switch-case切记break！！

3、思路

1）设两个堆栈，一个运算符栈，一个数字栈。

2）从左至右依次遍历字符串。若遍历到运算符，入运算符栈；若遍历到数字，则开始拼接数字，完成后入数字栈。 3）开始计算。 1>若运算符栈栈顶运算符为 × 、/，则弹出栈顶运算符，再从数字栈中依次弹出两个栈顶数字，完成运算后，将结果压入数字栈。 2>若运算符栈栈顶运算符为 + 、- 且栈顶下一个运算符为 × 、/，则弹出栈顶运算符和栈顶数字，保存。然后，弹出当前栈顶运算符，再从数字栈中依次弹出两个栈顶数字，完成运算后，将结果压入数字栈。最后，把刚刚保存的运算符和数字压栈。 4）若运算符栈为空，则运算结束，此时数字栈中唯一的数字即为表达式的值，显示后，弹出，为下一轮运算清空栈。

4、代码

#include 
   
    #include 
    
     #include 
     
      #include 
      
       using namespace std;#define N 200stack
       
         op;                 //运算符栈stack
        
          num; //操作数栈double a,b; //两个操作数double add(){ a = num.top(); num.pop(); b = num.top(); num.pop(); return (a+b);}double jianfa(){ a = num.top(); num.pop(); b = num.top(); num.pop(); return (b-a);}double mul(){ a = num.top(); num.pop(); b = num.top(); num.pop(); return (a*b);}double div(){ a = num.top(); num.pop(); b = num.top(); num.pop(); return (b/a);}int main(){ string input_string; char c,t; double value = 0; //使用getline读取，可以读取空格和换行 while(getline(cin,input_string)!=0) { if(input_string=="0") { continue; } //从字符串开头开始遍历，入操作数栈和运算符栈 for(int i=0 ; i
         
          ='0') { while(c<='9'&&c>='0') { value = value*10 +(double)(c-'0'); i++; c = input_string[i]; } num.push(value); value = 0; } else { i++; } } while(!op.empty()) { c = op.top(); op.pop(); switch(c) { case '+': if(op.empty()) { num.push(add()); } else { t = op.top(); if(t=='+'||t=='-') { num.push(add()); } else if(t=='*') { op.pop(); double number = num.top(); num.pop(); num.push(mul()); num.push(number); op.push(c); } else if(t=='/') { op.pop(); double number = num.top(); num.pop(); num.push(div()); num.push(number); op.push(c); } } break; case '-': if(op.empty()) { num.push(jianfa()); } else { t = op.top(); if(t=='+'||t=='-') { num.push(jianfa()); } else if(t=='*') { op.pop(); double number = num.top(); num.pop(); num.push(mul()); num.push(number); op.push(c); } else if(t=='/') { op.pop(); double number = num.top(); num.pop(); num.push(div()); num.push(number); op.push(c); } } break; case '*': num.push(mul()); break; case '/': num.push(div()); break; } } if(!num.empty()) { cout << fixed <
          
           <
           
            <
           
          
         
        
       
      
     
    
   

转载地址：http://osqqf.baihongyu.com/