資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法學研究C++ 帶替換的平衡表示式
括號的平衡表示式是指包含所有型別括號的配對，且順序正確的表示式。這意味著每個左括號都有一個對應的右括號，並且括號的順序正確，例如 { }。
讓我們來看幾個例子，以便更好地理解這個概念：
表示式 − {([][]{})({}[]{})}
輸出 − 平衡
解釋 − 我們可以看到，每個左括號都有一個對應的右括號。所有位於一對左括號和右括號之間的括號都是成對的。
輸出 − 不平衡
解釋 − 有一些括號的順序不對，使得表示式不平衡。
在這個被稱為“帶替換的平衡表示式”的問題中，我們得到一個字串，其中包含這些括號 ‘{’ , ‘}’ , ‘[’ , ‘]’ , ‘(’ , ‘)’ 。有些地方缺少括號，用“*”代替。我們必須檢查是否可以透過用合適的括號替換所有星號符號，使給定的表示式成為有效的表示式。
示例
輸入 − exp = “{[*(*)]}”
輸出 − 表示式可以平衡
解釋 − 有兩個符號需要替換。替換後將變成 {[(())]}。
輸入 − exp = “[(*){}{{}}]”
輸出 − 表示式無法平衡
解釋 − 有一個符號需要替換。用任何括號替換 * 後，表示式都無法平衡。
現在，既然我們對問題有了清晰的理解，我們可以為這個問題生成一個解決方案。為了檢查給定的括號表示式是否平衡，我們將使用堆疊資料結構來執行我們的任務。
為了完成此任務而執行的操作是：
遍歷字串表示式的每個元素並執行：
當在表示式中遇到左括號，即 ‘{’ , ‘[’ , ‘(’ 時，將元素壓入堆疊。
當在表示式中遇到右括號，即 ‘}’ , ‘]’ , ‘)’ 時，彈出堆疊頂部的元素，並檢查這是否是遇到的右括號對應的左括號。
如果兩個括號匹配，則移動到表示式的下一個元素（步驟 1）。
如果兩個括號不匹配，則表示式不平衡。
當在表示式中遇到 * 時，它可以是左括號也可以是右括號。然後：
首先將其視為左括號並將其壓入堆疊，並使用遞迴呼叫為下一個元素查詢匹配的右括號。如果結果為假，則執行下一步
將其視為右括號，它必須與堆疊頂部匹配，然後彈出堆疊頂部。
如果 * 的右括號與左括號不匹配，則返回不平衡。
根據結果列印語句。
示例
基於此解決方案，讓我們建立一個程式
#include <bits/stdc++.h>
using namespace std;
int isMatching(char a, char b){
if ((a == '{' & b == '}') || (a == '[' & b == ']') || (a == '(' & b == ')') || a == '*')
return 1;
return 0;
}
int isBalancedexpression(string s, stack<char> ele, int ind){
if (ind == s.length())
return ele.empty();
char topEle;
int res;
if (s[ind] == '{' || s[ind] == '(' || s[ind] == '[') {
ele.push(s[ind]);
return isBalancedexpression(s, ele, ind + 1);
}
else if (s[ind] == '}' || s[ind] == ')' || s[ind] == ']') {
if (ele.empty())
return 0;
topEle = ele.top();
ele.pop();
if (!isMatching(topEle, s[ind]))
return 0;
return isBalancedexpression(s, ele, ind + 1);
}
else if (s[ind] == '*') {
stack<char> tmp = ele;
tmp.push(s[ind]);
res = isBalancedexpression(s, tmp, ind + 1);
if (res)
return 1;
if (ele.empty())
return 0;
ele.pop();
return isBalancedexpression(s, ele, ind + 1);
}
}
int main(){
string s = "{[*(*)]}";
stack ele;
if (isBalancedexpression(s, ele, 0))
cout << "Balanced";
else
cout << "Not Balanced";
return 0;
}輸出
Balanced
318 次檢視
