c++栈实现，检查括号正确性

Question

我想通过CIN给出括号形式的表达式，如:())。然后，通过push &栈的pop操作，我希望程序打印我给定的表达式是平衡或不。程序运行完美，但只发现了一个问题& &;当我输入()(时，它告诉我这个表达式是不平衡的，这很好，但是当我输入() (时，它告诉我这个表达式是平衡的，这实际上是不平衡的。

#include <iostream>
/* run this program using the console pauser or add your own getch, system("pause") or input loop */
using namespace std;
char Stack[10];
int top=-1;
void push(char ch)
{
if(top<10)
{
top++;
Stack[top] = ch;
}
else
cout<<"Stack Overflow";
}
void pop()
{
if(top > -1)
{
top--;
}
else
cout<<"Stack Underflow";    
}
int show(){
cout<<"It is imbalanced.";
}
int main(int argc, char** argv) 
{

int a=0,b=0;
string exp;
cout << "Write down the parenthesis:" ;
cin >> exp;
bool check = true;

for(int i=0; i<exp.length(); i++)
{
if(exp[i]== '(')
{
push(exp[i]);
}
else if(exp[i]== ')')
{
if(top == -1)
{
check = false;
break;
}
else
{
pop();
}
}

}

for(int i=0; i<exp.length(); i++)
{
if(exp[i]=='('){
++a;
}
else if (exp[i]==')')
{
b++;

}   
}

if(a>b){
cout<<"nnGiven Combination is IMBALANCED";
return 0;
}

if(check == true)
cout<<"nnGiven Combination is BALANCED";

else
cout<<"nnGiven Combination is IMBALANCED";


return 0;
}

Answer 1

主要的注释可以归结为:

• 当不需要堆栈时不要使用堆栈。
  • 如果你使用一个，不要限制在一个任意的固定深度。
• 处理错误并报告错误表达式
• 确保你得到正确的输入;std::getline()可能比使用>>运算符的输入标记更不容易出错。只需跳过空格(或输入中允许的任何无关紧要的字符)。
• using namespace std;是一个反模式，也是一个坏习惯。

基本思想:在遍历字符串时计算嵌套的depth。它最终一定是零。它必须而不是

#include <cstdlib>
#include <iostream>
#include <stdexcept>
#include <string>
#include <string_view>
using std::size_t;
bool correctly_parenthesized(std::string_view expression) {
size_t depth{0};
for (const auto character : expression) {
switch (character) {
case '(': ++depth; break;
case ')': if (depth) { --depth; break; } else { return false; }
case ' ': break;
default: throw std::invalid_argument("invalid character");
}
}
return depth == 0;
}
int main() {
std::cout << "Write down the parentheses: ";
std::string exp;
std::getline(std::cin, exp);
try {
std::cout << (correctly_parenthesized(exp) ? "YES" : "NO") << std::endl;
} catch (const std::exception &e) {
std::cerr << e.what() << std::endl;
return EXIT_FAILURE;
}
}