用栈实现括号匹配（代码）

快来打我* 2023-01-03 04:20 6阅读 0赞

#include<iostream>
    #include<string>
    using namespace std;
    
    class LinkNode
    { 
    public:
    	LinkNode(const char v = '\0', LinkNode* p = NULL)
    	{ 
    		value = v;
    		next = p;
    	}
    	char value;
    	LinkNode* next;
    };
    
    class LinkStack
    { 
    public:
    	LinkStack();
    	~LinkStack();
    	void clear();
    	bool push(const char value);
    	bool pop(char & value);
    	bool isEmpty();
    private:
    	LinkNode *top;
    	int size;
    };
    
    LinkStack::LinkStack()
    { 
    	top = NULL;
    	size = 0;
    }
    
    LinkStack::~LinkStack()
    { 
    	clear();
    }
    
    void LinkStack::clear()
    { 
    	if (!top)
    		delete top;
    	size = 0;
    }
    
    bool LinkStack::push(const char value)
    { 
    	LinkNode* temp = new LinkNode(value, top);
    	top = temp;
    	size++;
    	return true;
    }
    
    bool LinkStack::pop(char & value)
    { 
    	LinkNode* temp = NULL;
    	if (!size)
    		return false;
    	value = top->value;
    	temp = top->next;
    	delete top;
    	top = temp;
    	size--;
    	return true;
    }
    
    bool LinkStack::isEmpty()
    { 
    	if (size != 0)
    		return false;
    	else
    		return true;
    }
    
    int main()
    { 
    	string exp;//表达式
    	char temp;//临时字符，用于处理表达式中各个字符
    	LinkStack Left;//左括号栈
    	cout << "请输入表达式：" << endl;
    	cin >> exp;
    	for (int i = 0; i < exp.length(); i++)
    	{ 
    		temp = exp[i];
    		switch (temp)
    		{ 
    		case '(':
    			Left.push(temp);
    			break;
    		case '[':
    			Left.push(temp);
    			break;
    		case '{':
    			Left.push(temp);
    			break;
    		case ')':
    			Left.pop(temp);
    			if (temp != '(')
    			{ 
    				cout << "括号配对错误！" << endl;
    				return 0;
    			}
    			break;
    		case ']':
    			Left.pop(temp);
    			if (temp != '[')
    			{ 
    				cout << "括号配对错误！" << endl;
    				return 0;
    			}
    			break;
    		case '}':
    			Left.pop(temp);
    			if (temp != '{')
    			{ 
    				cout << "括号配对错误！" << endl;
    				return 0;
    			}
    			break;
    		default:
    			break;
    		}
    	}
    	if (Left.isEmpty())
    		cout << "括号全部配对成功！" << endl;
    	else
    		cout << "括号配对错误！" << endl;
    	return 0;
    }