資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學列印根據給定語法表示式表示的單詞的排序列表
在本文中，我們將探討一個與表示式和語法相關的有趣問題。問題陳述是“列印根據給定語法表示式表示的單詞的排序列表”。這個問題提供了一個很好的機會來複習你關於解析表示式、處理字串和排序演算法的知識。
問題陳述
給定一個字串表示式，其中每個字元代表一個小寫英文字母，而字元“|”代表OR運算，任務是打印表達式表示的所有可能的單詞的排序列表。
解決方案方法
我們解決這個問題的方法是使用遞迴來解析表示式並生成所有可能的單詞。我們還將使用集合資料結構來儲存單詞並保持它們的排序。
示例
以下是實現此解決方案的程式：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
void generateWords(const char* expr, char* word, int wordIndex, int exprIndex, char** words, int* wordsCount) {
if (expr[exprIndex] == '\0') {
int duplicate = 0;
for (int i = 0; i < *wordsCount; i++) {
if (strcmp(words[i], word) == 0) {
duplicate = 1;
break;
}
}
if (!duplicate) {
strcpy(words[*wordsCount], word);
(*wordsCount)++;
}
return;
}
// Temporary storage for the current word to handle '|' character
char temp[100];
strcpy(temp, word);
// Loop through the expression to handle the characters and '|'
for (int i = exprIndex; expr[i] != '\0'; i++) {
if (expr[i] == '|') {
// Recursively generate words for the remaining expression after '|'
generateWords(expr, word, wordIndex, i + 1, words, wordsCount);
// Restore the original word to handle other characters
strcpy(word, temp);
} else {
// Add the character to the current word
word[wordIndex] = expr[i];
word[wordIndex + 1] = '\0'; // Null-terminate the string
// Recursively generate words for the remaining expression
generateWords(expr, word, wordIndex + 1, i + 1, words, wordsCount);
}
}
}
// Function to print the sorted list of words generated from the expression
void printWords(const char* expr) {
// Set to store the words (using a fixed-sized array of pointers)
char* words[100];
for (int i = 0; i < 100; i++) {
words[i] = (char*)malloc(100 * sizeof(char));
}
int wordsCount = 0; // To keep track of the number of words
// Generate the words from the expression
char word[100] = "";
generateWords(expr, word, 0, 0, words, &wordsCount);
printf("The sorted list of words is:\n");
for (int i = 0; i < wordsCount; i++) {
printf("%s\n", words[i]);
}
for (int i = 0; i < 100; i++) {
free(words[i]);
}
}
int main() {
const char* expr = "a|b|c";
printWords(expr);
return 0;
}
輸出
The sorted list of words is: abc ac bc c
#include <iostream>
#include <set>
#include <string>
using namespace std;
void generateWords(string expr, string word, set<string>& words) {
if (expr.empty()) {
words.insert(word);
return;
}
string temp = word;
for (int i = 0; i < expr.size(); i++) {
if (expr[i] == '|') {
generateWords(expr.substr(i + 1), word, words);
word = temp;
} else {
word.push_back(expr[i]);
}
}
words.insert(word);
}
void printWords(string expr) {
set<string> words;
generateWords(expr, "", words);
for (const string& word : words) {
cout << word << endl;
}
}
int main() {
string expr = "a|b|c";
cout << "The sorted list of words is: " << endl;
printWords(expr);
return 0;
}
輸出
The sorted list of words is: abc ac bc c
import java.util.HashSet;
import java.util.Set;
import java.util.TreeSet;
public class Main {
static void generateWords(String expr, String word, Set<String> words) {
if (expr.isEmpty()) {
words.add(word);
return;
}
String temp = word;
for (int i = 0; i < expr.length(); i++) {
if (expr.charAt(i) == '|') {
generateWords(expr.substring(i + 1), word, words);
word = temp;
} else {
word += expr.charAt(i);
}
}
words.add(word);
}
static void printWords(String expr) {
Set<String> words = new TreeSet<>();
generateWords(expr, "", words);
for (String word : words) {
System.out.println(word);
}
}
public static void main(String[] args) {
String expr = "a|b|c";
System.out.println("The sorted list of words is:");
printWords(expr);
}
}
輸出
The sorted list of words is: abc ac bc c
def generate_words(expr, word, words):
if len(expr) == 0:
words.add(word)
return
temp = word
for i in range(len(expr)):
if expr[i] == '|':
generate_words(expr[i + 1:], word, words)
word = temp
else:
word += expr[i]
words.add(word)
def print_words(expr):
words = set()
generate_words(expr, "", words)
for word in sorted(words):
print(word)
expr = "a|b|c"
print("The sorted list of words is:")
print_words(expr)
輸出
The sorted list of words is: abc ac bc c
帶測試用例的解釋
讓我們考慮表示式“a|b|c”。
當我們將此表示式傳遞給printWords函式時，它會生成表示式表示的所有可能的單詞，並將它們儲存在一個集合中以保持它們的排序。
可能的單詞是“abc”（組合所有字元）、“ac”（刪除'b'）、“bc”（刪除'a'）和“c”（刪除'a'和'b'）。
然後，該函式列印單詞的排序列表，即“abc”、“ac”、“bc”、“c”。
因此，根據給定的程式碼和問題陳述，你得到的輸出確實是正確的。對於之前的混淆，我深感抱歉。
結論
這個問題提供了一個很好的機會來練習解析表示式和使用遞迴生成序列。這是一個練習你的編碼技能並理解如何使用遞迴和集合資料結構進行問題解決的優秀問題。
更新於：2023年10月27日
127 次瀏覽
廣告