資料結構
網路
關係資料庫管理系統(RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學查詢給定C++表示式的所有可能結果
假設我們有一個沒有括號的算術表示式。我們的任務是找到該表示式的所有可能結果。假設表示式類似於1+2*3-4，可以解釋如下：
- 1+(2*(3-4)) = 1 + (2* -1) = -1
- (1+2)*(3-4) = 3 * -1 = -3
- 1+((2*3)-4) = 1 + (6 - 4) = 3
- ((1+2)*3)-4 = (3 * 3) - 4 = 5
- 1+(2*3)-4 = 1 + 6 – 4 = 3
為了解決這個問題，我們必須遵循以下步驟：
最初將res設定為為空
對於每個運算子x，執行以下操作：
遞迴地計算x左邊的所有可能值，將值列表設為L
遞迴地計算x右邊的所有可能值，將值列表設為R
迴圈遍歷L中的所有值
迴圈遍歷R中的所有值
對L和R中的當前元素應用當前運算子x，並將計算出的值新增到res中
- 返回res作為輸出
示例
#include<iostream>
#include<vector>
using namespace std;
int solve(int a, char op, int b) {
if (op=='+')
return a+b;
if (op=='-')
return a-b;
if (op == '*')
return a*b;
}
vector<int> getAllResults(string expr, int low, int high) {
vector<int> res;
if (low == high) {
res.push_back(expr[low] - '0');
return res;
}
if (low == (high-2)) {
int num = solve(expr[low]-'0', expr[low+1], expr[low+2]-'0');
res.push_back(num);
return res;
}
for (int i=low+1; i<=high; i+=2) {
vector<int> L = evaluateAll(expr, low, i-1);
vector R = evaluateAll(expr, i+1, high);
for (int s1=0; s1<L.size(); s1++) {
for (int s2=0; s2<R.size(); s2++) {
int val = solve(L[s1], expr[i], R[s2]);
res.push_back(val);
}
}
}
return res;
}
int main() {
string expr = "1+2*3-4";
vector<int> ans = getAllResults(expr, 0, expr.length()-1);
for (int i=0; i< ans.size(); i++)
cout << ans[i] << endl;
}輸出
2 1 4 3 5 6 7 8
更新於：2019年12月18日
212 次瀏覽
廣告