时间戳

首页 > 解决方案 > C ++：使用堆栈检查字符串中括号和括号的顺序是否正确

c++ - C ++：使用堆栈检查字符串中括号和括号的顺序是否正确

问题描述

我必须使用 pop() 和 push() 创建一个函数来检查括号和方括号的顺序是否正确，例如 "( ( [ [ ] ] ) )" 是正确的，但是 "( ( ( [ ] ] ] ） ）“ 不是。

我的想法是创建一个循环，并为每次迭代从字符串中获取一个字符并检查它是否是一个开头（括号或括号）然后推送它，如果它是一个关闭然后检查堆栈中的 top() 是否是一个开头同样，如果不是则返回false，如果是则pop()并继续循环，直到字符串结束。

问题是我不知道为什么我的代码不起作用。

提前致谢！

#include <iostream>
#include <stack>  
using namespace std;

bool checkExpress(string str){
    int i;
    stack <char> st;
    
    if(str.length() % 2 != 0) return false;
    
    for(i=0; i < str.length(); i++){

        if(str[i] == '(' || str[i] == '[') st.push(str[i]);
        
        else if(str[i] == ')' || str[i] == ']'){

            if(str[i] == ']' && st.top() != '[') return false;

            else if(str[i] == ')' && st.top() != '(') return false;
        }

        st.pop();   
    }

    return true;
}


int main(){
    string a = "(([[]]))";
    
    if(checkExpress(a)) cout << "The expression is well constructed.";
    else cout << "The expression is not well constructed.";

    return 0;
}

标签： c++

解决方案

改变

    }

    st.pop();

至

        st.pop();
    }

或更完整地说：

for(char ch : str){
  if (ch == '(' || ch == '[') {
    st.push(ch);
    continue;
  }
  if (st.empty())
    return false;
  char top = st.top();
  st.pop();
  
  if (top == '(' && ch==')')
    continue; // we good
  if (top == '[' && ch==']')
    continue; // we good

  return false; // invalid character, or bad match
}

这是一种提前退出的风格；我们尽可能早地做状态工作，然后在我们知道我们有这个循环的正确答案时退出（继续循环，或者返回）。

我们从开括号的情况开始；我们推动状态和循环，因为我们已经完成了。

然后，如果字符串是有效的，它必须有一个闭括号。所以我们首先进行状态转换，涵盖“文书工作”。然后我们验证我们是好的；如果是，我们所要做的就是继续，因为所有的州文书工作都已完成。

作为附带奖励，'('和在')'视觉上排列。:)

推荐阅读