c++ - 使用C++匹配圆括号、大括号和方括号

Question

我们应该使用 C++ 中的堆栈结构为我的 CS 类实现一个程序来检查给定表达式中的大括号、方括号和括号是否都匹配。不幸的是，我有点坚持这个，因为我一直告诉我有些东西不匹配，即使它最明确地匹配。这是我到目前为止得到的：

#include <stdlib.h>
#include <iostream>
#include <string>
#include <cstring>
using namespace std;

struct cell {int value; cell* next; };
cell* top;
int numElem;

void init()
{
    top = NULL;
    numElem = 0;
}

int pop()
{
    int res;
    if (top != NULL)
    {
        res = top -> value;
        top = top -> next;
        numElem--;
    } else {
        cout << "FAIL: Stack empty!\n";
        res = -1;
    }
    return res;
}

void push(int element)
{
    cell* cat = new cell;
    cat -> value = element;
    cat -> next = top;
    top = cat;
}

void match(char expr[])
{
    bool pass = true;
    char expected;
    char encountered;
    char closing;
    for (int i=0; pass && (i<strlen(expr)); i++)
    {
        if ((i==40)||(i==91)||(i==123))
            push(i);
        else 
        {
            if (i==41)
                expected = 40;
            if (i==93)
                expected = 91;
            if (i==125)
                expected = 123;
            encountered = pop();
            if (expected != encountered)
                closing = i;
                pass = false;
        }
    }
    if (pass)
        cout << "Parentheses match OK!\n";
    else
        cout << encountered << " has opened, but closing " << closing;
        cout << " encountered!\nParentheses do not match\n";
}

int main(int argc, char * argv[])
{
    init();
    match(argv[1]);
    return 0;
}

由于堆栈框架存在于先前的练习中并且在那里运行良好，我强烈假设应该存在任何错误void match

Answer 1

else
    cout << encountered << " has opened, but closing " << closing;
    cout << " encountered!\nParentheses do not match\n";

第二行总是打印。它应该是

else
{
    cout << encountered << " has opened, but closing " << closing;
    cout << " encountered!\nParentheses do not match\n";
}

还

if (expected != encountered)
            closing = i;
            pass = false;

也应该是

if (expected != encountered)
{
            closing = i;
            pass = false;
}

你来自python吗？缩进不会影响 C++ 中的逻辑，它只会影响可读性。

Answer 2

在您的匹配功能中，您应该测试字符，而不是它们的索引：

void match(char expr[])
{
...
    for (int i=0; pass && (i<strlen(expr)); i++)
    {
        char c = expr[i]; // use this c instead of i below!!!!!!!
        if ((c==40)||(c==91)||(c==123))
            push(c);
        else 
        {
            if (c==41)
                expected = 40;
            if (c==93)
                expected = 91;
            if (c==125)
...

您也没有在推送中更新计数器：

void push(int element)
{
...
   ++numElems; // Was missing!!!!
}