检测圆括号，括号和大括号是否平衡的c++程序-需要在错误下输出插入符号

Question

我需要编写一个程序，使用堆栈来验证字符串表达式是否平衡，关于其中包含的括号，括号和花括号。字符串将由用户输入，所有错误(即不匹配的圆括号、括号和花括号)都需要在下一行用插入符号指出，就在它的正下方，像这样:

(这里有点难展示…)

(()

^

在我的"balanced"函数中，我取循环的当前索引，并将其分配给"unmatchedRightPosition"或"unmatchedLeftPosition"，即当时需要的任何一个。我认为我的很多程序已经工作了，但我在错误下放置插入符号时遇到了问题。我的教授建议我可以选择使用一个保存结构体的堆栈类，其中每个结构体都包含一个char和char的位置，但我对此有点困惑。

Thanks for looking

#include <iostream>
#include <string>
#include <stdlib.h>
#include <sstream>
using namespace std;
struct Stack{
    static const unsigned MAX_SIZE = 5;
    char data[ MAX_SIZE ];
    unsigned size;
};
struct Stack2{
 unsigned unmatchedLeftPos, unmatchedRightPos;
};
void initialize( Stack & stack );
void show( const Stack & stack );
unsigned getSize( const Stack & stack );
void push( Stack & stack, char c );
char pop( Stack & stack );
char top( const Stack & stack );
bool die( const string & msg );
bool balanced (unsigned & unmatchedLeftPos, unsigned & unmatchedRightPos, const string & expr);
int main(){

    Stack2 s2;
    cout << "nPlease enter your expression - enter a blank line to quit. n";
    for(;;){
        string line;
        getline(cin, line);

        if( line.size() == 0 )  break;
            if (balanced(s2.unmatchedLeftPos, s2.unmatchedRightPos, line) == 1){
                cout << "OKn";
            }
            else if (balanced(s2.unmatchedLeftPos, s2.unmatchedRightPos, line) == 0){
            cout << string(s2.unmatchedLeftPos, ' ') << '^';
            cout << string(s2.unmatchedRightPos, ' ') << '^';
            }
        }
        return 0;
    }
void initialize( Stack & stack ){
    stack.size = 0;
}
void show( const Stack & stack ){
    cout <<"[" << stack.size <<"]:";
    for(  unsigned i = 0;  i < stack.size;  i++  )
        cout <<stack.data[i];
    cout <<endl;
} // show
unsigned getSize( const Stack & stack ) {return stack.size;}
void push( Stack & stack, char c ){
    if( stack.size == Stack::MAX_SIZE )  die( "push: overflow" );
    stack.data[stack.size++] = c;
} // push
char pop( Stack & stack ){
    if( stack.size == 0 )  die( "pop: underflow" );
    return stack.data[--stack.size];
} // pop
char top( const Stack & stack ){
    if( stack.size == 0 )  die( "top: underflow" );
    return stack.data[stack.size-1];
} // pop
bool die( const string & msg ){
    cerr <<endl <<"Fatal error: " << msg <<endl;
    exit( EXIT_FAILURE );
}
bool balanced (unsigned & unmatchedLeftPos, unsigned & unmatchedRightPos, const string & expr){
    Stack s;
    initialize(s);
    unsigned i;
    for (i = 0; i < expr.size(); i++){
        char c = expr[i];
        if( expr.size() == Stack::MAX_SIZE)  {
                die( "push: overflow" );
            }
        if (c == '(')
        {
            push(s, c);
        }
        else if (c == '['){
            push(s, c);
        }
        else if (c == '{'){
            push(s, c);
        }
        if (s.size == 0 && (c == ')' || c == ']' || c == '}'))
        {
            unmatchedRightPos = i;
            return false;
        }
        else if (c == ')' && top(s) == '('){
            pop(s);
        }
        else if (c == ']' && top(s) == '['){
            pop(s);
        }
        else if (c == '}' && top(s) == '{'){
            pop(s);
        }
    }
    if (s.size == 0){
        return true;
    }
    else if (top(s) == '(' || top(s) == '[' || top(s) == '{'){
        unmatchedLeftPos = i;
        return false;
    }
}

Answer 1

您当前正在使用堆栈，其中包含一个字符数组:

char data[ MAX_SIZE ];

相反，您应该使用结构体，它保存输入字符串

中的字符和位置。

struct info {
    char data;
    int pos;
};
info data[ MAX_SIZE ];

所以在最后，你只是检查你的堆栈，除了无效字符，你也有输入字符串中的位置。

希望对你有帮助。

Answer 2

可以将main移到底部，以避免前向函数声明。您也不需要使用另一个堆栈来处理错误(实际上，我认为如果不这样做会更容易)。你只需要同时保存括号和它在一个堆栈中的位置，即

struct Item
{
    char bracket;
    size_t position;
}
std::stack<Item> st;

也可以是一个数组，或者最好是一个字符串，初始化为与输入字符串相同的长度，所有空格在遇到错误时更改为'^'，即

std::string errorString(input.size(), ' ');
if ( /* brackets don't match */ )
{
    errorString[st.top().position] = '^';
}

如果你不能使用STL栈，你需要修改自己的栈来保存Item对象而不是char对象(即Item data[MAX_SIZE];)。你的代码看起来很像C的想法，它会更好，如果你使用std::string和std::stack代替。