A. 編譯原理
C語言編譯過程詳解
C語言的編譯鏈接過程是要把我們編寫的一個C程序(源代碼)轉換成可以在硬體上運行的程序(可執行代碼)，需要進行編譯和鏈接。編譯就是把文本形式源代碼翻譯為機器語言形式的目標文件的過程。鏈接是把目標文件、操作系統的啟動代碼和用到的庫文件進行組織形成最終生成可執行代碼的過程。過程圖解如下：
從圖上可以看到，整個代碼的編譯過程分為編譯和鏈接兩個過程，編譯對應圖中的大括弧括起的部分，其餘則為鏈接過程。
一、編譯過程
編譯過程又可以分成兩個階段：編譯和匯編。
1、編譯
編譯是讀取源程序(字元流)，對之進行詞法和語法的分析，將高級語言指令轉換為功能等效的匯編代碼，源文件的編譯過程包含兩個主要階段：
第一個階段是預處理階段，在正式的編譯階段之前進行。預處理階段將根據已放置在文件中的預處理指令來修改源文件的內容。如#include指令就是一個預處理指令，它把頭文件的內容添加到.cpp文件中。這個在編譯之前修改源文件的方式提供了很大的靈活性，以適應不同的計算機和操作系統環境的限制。一個環境需要的代碼跟另一個環境所需的代碼可能有所不同，因為可用的硬體或操作系統是不同的。在許多情況下，可以把用於不同環境的代碼放在同一個文件中，再在預處理階段修改代碼，使之適應當前的環境。
主要是以下幾方面的處理：
(1)宏定義指令，如 #define a b。
對於這種偽指令，預編譯所要做的是將程序中的所有a用b替換，但作為字元串常量的 a則不被替換。還有 #undef，則將取消對某個宏的定義，使以後該串的出現不再被替換。
(2)條件編譯指令，如#ifdef，#ifndef，#else，#elif，#endif等。
這些偽指令的引入使得程序員可以通過定義不同的宏來決定編譯程序對哪些代碼進行處理。預編譯程序將根據有關的文件，將那些不必要的代碼過濾掉
(3) 頭文件包含指令，如#include "FileName"或者#include <FileName>等。
在頭文件中一般用偽指令#define定義了大量的宏(最常見的是字元常量)，同時包含有各種外部符號的聲明。採用頭文件的目的主要是為了使某些定義可以供多個不同的C源程序使用。因為在需要用到這些定義的C源程序中，只需加上一條#include語句即可，而不必再在此文件中將這些定義重復一遍。預編譯程序將把頭文件中的定義統統都加入到它所產生的輸出文件中，以供編譯程序對之進行處理。包含到C源程序中的頭文件可以是系統提供的，這些頭文件一般被放在/usr/include目錄下。在程序中#include它們要使用尖括弧(<>)。另外開發人員也可以定義自己的頭文件，這些文件一般與C源程序放在同一目錄下，此時在#include中要用雙引號("")。
(4)特殊符號，預編譯程序可以識別一些特殊的符號。
例如在源程序中出現的LINE標識將被解釋為當前行號(十進制數)，FILE則被解釋為當前被編譯的C源程序的名稱。預編譯程序對於在源程序中出現的這些串將用合適的值進行替換。
預編譯程序所完成的基本上是對源程序的「替代」工作。經過此種替代，生成一個沒有宏定義、沒有條件編譯指令、沒有特殊符號的輸出文件。這個文件的含義同沒有經過預處理的源文件是相同的，但內容有所不同。下一步，此輸出文件將作為編譯程序的輸出而被翻譯成為機器指令。
第二個階段編譯、優化階段。經過預編譯得到的輸出文件中，只有常量；如數字、字元串、變數的定義，以及C語言的關鍵字，如main,if,else,for,while,{,}, +,-,*,\等等。
編譯程序所要作得工作就是通過詞法分析和語法分析，在確認所有的指令都符合語法規則之後，將其翻譯成等價的中間代碼表示或匯編代碼。
優化處理是編譯系統中一項比較艱深的技術。它涉及到的問題不僅同編譯技術本身有關，而且同機器的硬體環境也有很大的關系。優化一部分是對中間代碼的優化。這種優化不依賴於具體的計算機。另一種優化則主要針對目標代碼的生成而進行的。
對於前一種優化，主要的工作是刪除公共表達式、循環優化(代碼外提、強度削弱、變換循環控制條件、已知量的合並等)、復寫傳播，以及無用賦值的刪除，等等。
後一種類型的優化同機器的硬體結構密切相關，最主要的是考慮是如何充分利用機器的各個硬體寄存器存放的有關變數的值，以減少對於內存的訪問次數。另外，如何根據機器硬體執行指令的特點(如流水線、RISC、CISC、VLIW等)而對指令進行一些調整使目標代碼比較短，執行的效率比較高，也是一個重要的研究課題。
2、匯編
匯編實際上指把匯編語言代碼翻譯成目標機器指令的過程。對於被翻譯系統處理的每一個C語言源程序，都將最終經過這一處理而得到相應的目標文件。目標文件中所存放的也就是與源程序等效的目標的機器語言代碼。目標文件由段組成。通常一個目標文件中至少有兩個段：
代碼段：該段中所包含的主要是程序的指令。該段一般是可讀和可執行的，但一般卻不可寫。
數據段：主要存放程序中要用到的各種全局變數或靜態的數據。一般數據段都是可讀，可寫，可執行的。
UNIX環境下主要有三種類型的目標文件：
(1)可重定位文件
其中包含有適合於其它目標文件鏈接來創建一個可執行的或者共享的目標文件的代碼和數據。
(2)共享的目標文件
這種文件存放了適合於在兩種上下文里鏈接的代碼和數據。
第一種是鏈接程序可把它與其它可重定位文件及共享的目標文件一起處理來創建另一個 目標文件；
第二種是動態鏈接程序將它與另一個可執行文件及其它的共享目標文件結合到一起，創建一個進程映象。
(3)可執行文件
它包含了一個可以被操作系統創建一個進程來執行之的文件。匯編程序生成的實際上是第一種類型的目標文件。對於後兩種還需要其他的一些處理方能得到，這個就是鏈接程序的工作了。
二、鏈接過程
由匯編程序生成的目標文件並不能立即就被執行，其中可能還有許多沒有解決的問題。
例如，某個源文件中的函數可能引用了另一個源文件中定義的某個符號(如變數或者函數調用等)；在程序中可能調用了某個庫文件中的函數，等等。所有的這些問題，都需要經鏈接程序的處理方能得以解決。
鏈接程序的主要工作就是將有關的目標文件彼此相連接，也即將在一個文件中引用的符號同該符號在另外一個文件中的定義連接起來，使得所有的這些目標文件成為一個能夠被操作系統裝入執行的統一整體。
根據開發人員指定的同庫函數的鏈接方式的不同，鏈接處理可分為兩種：
(1)靜態鏈接
在這種鏈接方式下，函數的代碼將從其所在地靜態鏈接庫中被拷貝到最終的可執行程序中。這樣該程序在被執行時這些代碼將被裝入到該進程的虛擬地址空間中。靜態鏈接庫實際上是一個目標文件的集合，其中的每個文件含有庫中的一個或者一組相關函數的代碼。
(2) 動態鏈接
在此種方式下，函數的代碼被放到稱作是動態鏈接庫或共享對象的某個目標文件中。鏈接程序此時所作的只是在最終的可執行程序中記錄下共享對象的名字以及其它少量的登記信息。在此可執行文件被執行時，動態鏈接庫的全部內容將被映射到運行時相應進程的虛地址空間。動態鏈接程序將根據可執行程序中記錄的信息找到相應的函數代碼。
對於可執行文件中的函數調用，可分別採用動態鏈接或靜態鏈接的方法。使用動態鏈接能夠使最終的可執行文件比較短小，並且當共享對象被多個進程使用時能節約一些內存，因為在內存中只需要保存一份此共享對象的代碼。但並不是使用動態鏈接就一定比使用靜態鏈接要優越。在某些情況下動態鏈接可能帶來一些性能上損害。
我們在linux使用的gcc編譯器便是把以上的幾個過程進行捆綁，使用戶只使用一次命令就把編譯工作完成，這的確方便了編譯工作，但對於初學者了解編譯過程就很不利了，下圖便是gcc代理的編譯過程：
從上圖可以看到：
預編譯
將.c 文件轉化成 .i文件
使用的gcc命令是：gcc –E
對應於預處理命令cpp
編譯
將.c/.h文件轉換成.s文件
使用的gcc命令是：gcc –S
對應於編譯命令 cc –S
匯編
將.s 文件轉化成 .o文件
使用的gcc 命令是：gcc –c
對應於匯編命令是 as
鏈接
將.o文件轉化成可執行程序
使用的gcc 命令是： gcc
對應於鏈接命令是 ld
總結起來編譯過程就上面的四個過程：預編譯、編譯、匯編、鏈接。了解這四個過程中所做的工作，對我們理解頭文件、庫等的工作過程是有幫助的，而且清楚的了解編譯鏈接過程還對我們在編程時定位錯誤，以及編程時盡量調動編譯器的檢測錯誤會有很大的幫助的。
是否可以解決您的問題？
B. 編譯原理問題：求解
E是文法開頭。ε代表終結符號(推理中代表終點或結果，程序語言中代表常量等)。E T 這些大寫字母一般代表非終結符號（這些代表中間過程，非結果。程序中代表函數等等）。開始是E。因為有個G(E)。E就是文法開始符號。推導就有E開始，它也是一個非終結符(代表函數、或者一個推導過程，類似於程序中的main(c++)、winmain(vc++)、dllmain(dll)等主函數）。
1算術表達式文法：這個文法是一個遞歸文法。計算機進行邏輯推導時會走很多彎路（類似於遍歷一顆樹的過程）。為了不讓計算機走彎路（提高效率的目的），可以變換為第二種文法。這種文法消除了遞歸（消除了歧義，類似於後綴表達式），使計算機可以一條直線走到底兒推導出結果。
我也很久沒看編譯原理了。 呵呵
C. 【編譯原理】第二章：語言和文法
上述文法 表示，該文法由終結符集合 ，非終結符集合 ，產生式集合 ，以及開始符號 構成。
而產生式 表示，一個表達式（Expression） ，可以由一個標識符（Identifier） 、或者兩個表達式由加號 或乘號 連接、或者另一個表達式用括弧包裹（ ）構成。
約定 ：在不引起歧義的情況下，可以只寫產生式。如以上文法可以簡寫為：
產生式
可以簡寫為：
如上例中，
可以簡寫為：
給定文法 ，如果有 ，那麼可以將符號串 重寫 為 ，記作 ，這個過程稱為 推導 。
如上例中， 可以推導出 或 或 等等。
如果 ，
可以記作 ，則稱為 經過n步推導出 ，記作 。
推導的反過程稱為 歸約 。
如果 ，則稱 是 的一個 句型（sentential form ）。
由文法 的開始符號 推導出的所有句子構成的集合稱為 文法G生成的語言 ，記作 。
即：
例
文法
表示什麼呢？
代表小寫字母；
代表數字；
表示若干個字母和數字構成的字元串；
說明 是一個字母、或者是字母開頭的字元串。
那麼這個文法表示的即是，以字母開頭的、非空的字元串，即標識符的構成方式。
並、連接、冪、克林閉包、正閉包。
如上例表示為：
中必須包含一個 非終結符 。
產生式一般形式：
即上式中只有當上下文滿足 與 時，才能進行從 到 的推導。
上下文有關文法不包含空產生式（ ）。
產生式的一般形式：
即產生式左邊都是非終結符。
右線性文法 ：
左線性文法 ：
以上都成為正則文法。
即產生式的右側只能有一個終結符，且所有終結符只能在同一側。
例：（右線性文法）
以上文法滿足右線性文法。
以上文法生成一個以字母開頭的字母數字串（標識符）。
以上文法等價於 上下文無關文法 ：
正則文法能描述程序設計語言中的多數單詞。
正則文法能描述程序設計語言中的多數單詞，但不能表示句子構造，所以用到最多的是CFG。
根節點 表示文法開始符號S；
內部節點 表示對產生式 的應用；該節點的標號是產生式左部，子節點從左到右表示了產生式的右部；
葉節點 （又稱邊緣）既可以是非終結符也可以是終結符。
給定一個句型，其分析樹的每一棵子樹的邊緣稱為該句型的一個 短語 。
如果子樹高度為2，那麼這棵子樹的邊緣稱為該句型的一個 直接短語 。
直接短語一定是某產生式的右部，但反之不一定。
如果一個文法可以為某個句子生成 多棵分析樹 ，則稱這個文法是 二義性的 。
二義性原因：多個if只有一個else；
消岐規則：每個else只與最近的if匹配。
D. 編譯原理有有符號un-1.u=un嗎
編譯程序把源程序翻譯為目標程序。根據源程序的語言種類，翻譯程序可以分為匯編程序與編譯程序。與之相對，解釋程序是對源程序進行解釋執行的程序。相應的可以將高級語言分為
編譯型 C/C++, Swift, etc.
解釋型 Python, javascript, etc.
混合型 Java, etc.
本文重點放在編譯程序的設計上。典型的編譯程序具有 7 77 個邏輯部分
對源程序掃描一次被稱為一遍 (pass)。典型的一遍掃描編譯程序有如下形式
通常將中間代碼生成前的分析部分稱為編譯器的前端，其後的綜合部分則被稱為後端。這樣就把一個編譯程序分為了與源語言相關和與目標機有關的兩個獨立的部分，降低了程序的耦合。假設 llvm 編譯器 支持 M MM 種源語言到 N NN 種目標語言的編譯
傳統的編譯器如 gcc 可能需要開發 M × N M \times NM×N 個不同的子模塊。而 llvm 使用統一的中間語言 llvm Intermediate Representation 只需要 M MM 個前端與 N NN 個後端，大大降低了開發成本。
文法
設非空有窮集合 Σ \SigmaΣ 為一字母表，則其上的符號串為 ∀ s ∈ Σ ∗ \forall s \in \Sigma^*∀s∈Σ
∗
，其中 ∗ *∗ 表示集合的閉包。特別的記 Σ 0 = ε \Sigma^0 = {\varepsilon}Σ
0
=ε 為空串組成的集合。規則通常寫作
U : : = x or U → x , ∣ U ∣ = 1 , ∣ x ∣ ≥ 0 U ::= x\text{ or }U\rightarrow x,\quad |U| = 1, |x| \ge 0U::=x or U→x,∣U∣=1,∣x∣≥0
其中左部 U UU 是符號，右部 x xx 是有窮符號串。規則的集合 P PP 即可確定一個文法 G GG
<程序> ::= <常量說明><變數說明><函數說明>
<常量說明> ::= {const<常量定義>;}
<常量定義> ::= int<標識符>=<整數>{,<標識符>=<整數>}|char<標識符>=<字元>{,<標識符>=<字元>}
<變數說明> ::= {<類型標識符><變數定義>;}
<變數定義> ::= <標識符>[<下標>]{,<標識符>[<下標>]}
<下標> ::= '['<無符號整數>']' // <無符號整數>表示數組元素的個數，其值需大於0
<函數說明> ::= {(<類型標識符>|void)<函數定義>}void<主函數>
<函數定義> ::= <標識符>'('<參數表>')'<復合語句>
<參數表> ::= [<類型標識符><標識符>{,<類型標識符><標識符>}]
<主函數> ::= main'('')'<復合語句>
<復合語句> ::= '{'<常量說明><變數說明>{<語句>}'}'
<語句> ::= <條件語句>|'{'{<語句>}'}'|<函數調用語句>;|<賦值語句>;|<讀語句>;|<寫語句>;|<返回語句>;|;
<條件語句> ::= <if語句>|<while語句>|<do語句>|<for語句>
<if語句> ::= if'('<條件>')'<語句>[else<語句>]
<while語句> ::= while'('<條件>')'<語句>
<do語句> ::= do<語句>while'('<條件>')'
<for語句> ::= for'('<標識符>=<表達式>;<條件>;<標識符>=<標識符><加法運算符><無符號整數>')'<語句>
<條件> ::= <表達式>[<關系運算符><表達式>] // 表達式為0條件為假，否則為真
<函數調用語句> ::= <標識符>'('[<表達式>{,<表達式>}]')'
<賦值語句> ::= <標識符>['['<表達式>']']=<表達式>
<讀語句> ::= scanf'('<標識符>{,<標識符>}')'
<寫語句> ::= printf'('<字元串>[,<表達式>]')'|printf'('<表達式>')'
<返回語句> ::= return['('<表達式>')']
<表達式> ::= [<加法運算符>]<項>{<加法運算符><項>} // [+|-]只作用於第一個<項>
<項> ::= <因子>{<乘法運算符><因子>}
<因子> ::= <標識符>['['<表達式>']']|'('<表達式>')'|<整數>|<字元>|<函數調用語句>
<整數> ::= [<加法運算符>]<無符號整數>
<標識符> ::= <字母>{<字母>|<數字>}
<無符號整數> ::= <非零數字>{<數字>}|0
<數字> ::= 0|<非零數字>
<非零數字> ::= 1|...|9
<字元> ::= '<加法運算符>'|'<乘法運算符>'|'<字母>'|'<數字>'
<字元串> ::= "{十進制編碼為32,33,35-126的ASCII字元}"
<類型標識符> ::= int|char
<加法運算符> ::= +|-
<乘法運算符> ::= *|/
<關系運算符> ::= <|<=|>|>=|!=|==
<字母> ::= _|a|...|z|A|...|Z
復制
上述文法使用擴充的 BNF 表示法進行描述
符號 定義 說明
∣ \vert∣ 或 作用域由括弧限定
{ t } n m \{t\}^m_n{t}
n
m
將 t tt 重復連接 n ∼ m n \sim mn∼m 次 預設時 m = ∞ , n = 0 m = \infin,\ n = 0m=∞, n=0
[ t ] [t][t] 符號串 t tt 可有可無 等價於 { t } 1 \{t\}^1{t}
1
( t ) (t)(t) 局部作用域 主要用於限定 ∣ \vert∣ 范圍
相關概念有
概念 符號 定義 示例
識別符號 Z ZZ 文法中第一條規則的左部符號 <程序>
字匯表 V VV 文法中出現的全部符號 { <程序>, <常量說明>, …, 0, 1, … }
非終結符號集 V n V_nV
n
全部規則的左部組成的集合 { <程序>, <常量說明>, <變數說明>, … }
終結符號集 V t V_tV
t
V − V n V - V_nV−V
n
{ 0, 1, …, _, a, b, … }
設 U : : = u ∈ P U ::= u \in PU::=u∈P 則對於 ∀ x , y ∈ V ∗ \forall x, y \in V^*∀x,y∈V
∗
有直接推導 x U y ⇒ x u y xUy \Rightarrow xuyxUy⇒xuy 。如果 y ∈ V t ∗ y \in V_t^*y∈V
t
∗
則 x U y ⤃ x u y xUy\ ⤃\ xuyxUy ⤃ xuy 稱為規范推導。直接推導序列 u 0 ⇒ u 1 ⇒ ⋯ ⇒ u n u_0 \Rightarrow u_1 \Rightarrow \cdots \Rightarrow u_nu
0
⇒u
1
⇒⋯⇒u
n
可簡記為
{ u 0 ⇒ + u n n > 0 u 0 ⇒ ∗ u n n ≥ 0 \begin{cases} u_0 \mathop\Rightarrow\limits^+ u_n & n > 0\\ u_0 \mathop\Rightarrow\limits^* u_n & n \ge 0\\ \end{cases}{
u
0
⇒
+
u
n
u
0
⇒
∗
u
n
n
>
0
n
≥
0
進一步定義
句型 V ∗ ∋ x ⇐ ∗ Z V^* \ni x \mathop\Leftarrow\limits^* ZV
∗
∋x
⇐
∗
Z
句子 V t ∗ ∋ x ⇐ + Z V_t^* \ni x \mathop\Leftarrow\limits^+ ZV
t
∗
∋x
⇐
+
Z
語言 L ( G ) = { x ∣ x is sentence } L(G) = \{ x| x\text{ is sentence} \}L(G)={x∣x is sentence}
如果文法 G GG 和 G ′ G'G
′
有 L ( G ) = L ( G ′ ) L(G) = L(G')L(G)=L(G
′
) ，則稱這兩個文法等價。設 w = x u y w=xuyw=xuy 為一句型，稱 u uu 為一個相對於 U ∈ V n U \in V_nU∈V
n
的
w ww 的短語 如果 Z ⇒ ∗ x U y ∧ U ⇒ + u Z \mathop\Rightarrow\limits^* xUy \land U \mathop\Rightarrow\limits^+ uZ
⇒
∗
xUy∧U
⇒
+
u
w ww 的簡單短語 如果 u uu 是短語且 U ⇒ u U \mathop\Rightarrow\limits uU⇒u
句型的最左簡單短語稱為句柄。
二義性
文法 G GG 是二義性的，如果 ∃ x ∈ L ( G ) \exist x \in L(G)∃x∈L(G) 使下列條件之一成立
x xx 可以對應兩顆不同的語法樹
x xx 有兩個不同的規范推導
E. java中的正則表達式跟編譯原理有什麼聯系
首先，正則表達式不僅在Java里有，其它語言裡面也有，它是一個數學上的概念，各個語言中的正則表達式是它的不同形式的實現。
其次，編譯原理的詞法分析里，會用到正則表達式去匹配源程序中的各種token(記號)，比如說
int a = 8;
里識別出：
類型名：int
變數名：a
運算符：=
數字：8
結尾分號：;
總之，二者有聯系，但不是一回事。
F. 試編程確定使得整個算式成立的數字組合，如有多種情況，請給出所有可能的答案。 l 計算24是流行的撲克游戲
/*
程序主要使用了正則表達式（編譯原理的內容）和計算用字元串表示的表達式兩種技術。
算24點的一般形式，用正則表達式表示有一下幾種：
( ( ( E O E ) O E ) O E ) = 24
( ( E O ( E O E ) ) O E ) = 24
( ( E O E ) O ( E O E ) ) = 24
( ( E O E ) O ( E O E ) ) = 24
( E O ( ( E O E ) O E ) ) = 24
( E O ( E O ( E O E ) ) ) = 24
其中 E 表示數字，O表示操作符 。
程序的思想就是窮舉法，把上面六個式子中的 E 用合法的數字替換，
O 用合法的操作符替換，看是否能得出結果。顯然計算結果時還要
計算字元串表示的表達式。
例如：( ( ( 1 + 2 ) + 3 ) * 4 ) = 24 就是一種替換 ，等號左邊是一個
用字元串表示的表達式。
這種方法的【優點】是思路簡單，而且容易擴展 。
（如不是用四個數字而是任意個，並且可以使用加減乘除以外的運算）
當然這種方法的【缺點】是產生大量我們一般認為重復的式子。
如 ( ( ( 1 + 2 ) + 3 ) * 4 ) = 24 和 ( ( 1 + ( 2 + 3 ) ) * 4 ) = 24
去掉不必要的括弧和，都能化成：
(1 + 2 + 3 )*4 = 24 ，因此一般我們認為上面這兩個式子是相同的。
*/
#include <iostream>
#include <cstring>
#include <cmath>
#include <string>
#include <ctime>
#include <cstdlib>
using namespace std;
const int MAX_AVAILABAL_NUMBER_NUM = 20;
const int MAX_AVAILABAL_OPERATOR_NUM = 10;
const int MAX_REGULAR_EXPRESSION_NUM = 100;
const int MAX_LEAGAL_EXPRESSION_NUM = 4000;
const int MAX_LEN = MAX_AVAILABAL_NUMBER_NUM * 10;
#define SAVE 0
#define PRINT 1
#define EMPTY -1
// 將整數 num 裝換成字元串保存著 s 中
char * Num_To_Str(char s[],int num)
{
int len = (int)log10(num)+1;
s[len--]='\0';
do
{
s[len--]=(num%10)+'0';
num/=10;
}while(num);
return s;
}
// 替換字元 s[p] 為字元串 t
char* Replace(char s[],int p,char t[])
{
int ls,lt,i,j,k;
ls = strlen(s);
lt = strlen(t);
for(i=ls+lt-1;i>=(p+lt);i--)
s[i]=s[i-lt+1];
for(j=p,k=0;t[k]!='\0';j++,k++)
s[j]=t[k];
return s;
}
typedef struct
{
int number;
int appear_time;
}Node;
//記錄產生表達式所需的信息
class Expression_Imformation
{
public:
void Init();
void Init_All_Answer();
void Init_Calculate();
void Init_Guess();
void Generate_Expression(char start[],char rule[],int T,int t);
void Calculate(int num_of_chose_number,int num_of_chose_operator);
int Precedence(char op);
double Calculate_Expression(char *S1,bool & Is_A_Leagal_Expression );
char* Transform(char *S1 ,bool & Is_A_Leagal_Expression);
private:
int num_of_used_number; // 產生表達式需要數據個數，默認為 4 個數據
double reslut; // 表達式的結果，默認為 24
// 可使用的數據范圍，默認 1-13，每個數據可出現多次
int num_of_available_number;
Node available_number[MAX_AVAILABAL_NUMBER_NUM];
// 可使用的符號類型，默認加減乘除
int num_of_available_operator;
char available_operator[MAX_AVAILABAL_OPERATOR_NUM][5];
// 正則表達式
// 如 ( ( E O E ) O ( E O E ))
// 其中 E 表示數據，O 表示操作符
int num_of_regular_expression;
char regular_expression[MAX_REGULAR_EXPRESSION_NUM][MAX_LEN];
// 符合結果的表達式
int num_of_leagal_expression;
char leagal_expression[MAX_LEAGAL_EXPRESSION_NUM][MAX_LEN];
//臨時變數，Generate_Expression 函數使用
int chose_number[MAX_AVAILABAL_NUMBER_NUM];
char chose_operator[MAX_AVAILABAL_NUMBER_NUM-1][5];
int save_or_print; // 控制結果直接輸出還是保存
};
void Expression_Imformation::Init()
{
num_of_used_number = 4;
reslut = 24.0;
num_of_available_operator = 4;
strcpy(available_operator[0],"+");
strcpy(available_operator[1],"-");
strcpy(available_operator[2],"*");
strcpy(available_operator[3],"/");
//產生正則表達式
num_of_regular_expression = 0;
char start[MAX_LEN] = "E";
char rule[MAX_LEN] = "( E O E )";
Generate_Expression(start,rule,num_of_used_number-1,0);
// cout<<num_of_regular_expression<<endl;
// for(int i=0;i<num_of_regular_expression;i++)
// cout<<i+1<<" "<<regular_expression[i]<<endl;
num_of_leagal_expression = 0;
save_or_print = PRINT;
}
void Expression_Imformation::Init_All_Answer()
{
Init();
cout<<"**********All_AnswerS**********"<<endl;
num_of_available_number = 13;
for(int i=0;i<num_of_available_number;i++)
{
available_number[i].number = i+1;
available_number[i].appear_time = num_of_used_number;
}
save_or_print = PRINT;
num_of_leagal_expression = 0;
Calculate(0,0);
}
void Expression_Imformation::Init_Calculate()
{
int i,j,temp;
char option[MAX_LEN];
Init();
while(1)
{
cout<<"***********Calculate***********"<<endl;
num_of_available_number = 0;
for(int i=0;i<num_of_used_number;i++)
{
cout<<"Input the "<<i+1<<"th number : ";
cin>>temp;
for(j=0;j<num_of_available_number;j++)
if(temp == available_number[j].number)
break;
if(j<num_of_available_number)
available_number[j].appear_time++;
else
{
available_number[j].number = temp;
available_number[j].appear_time = 1;
num_of_available_number++;
}
}
save_or_print = PRINT;
num_of_leagal_expression = 0;
Calculate(0,0);
if(num_of_leagal_expression == 0)
cout<<"No Solution!"<<endl;
cout<<"continue?(Y/N)"<<endl;
cin>>option;
if(!( strcmp(option,"Y")==0 || strcmp(option,"y")==0 ))
return ;
}
}
void Expression_Imformation::Init_Guess()
{
char option[MAX_LEN];
char answer[MAX_LEN];
int i,j,temp;
bool Is_A_Leagal_Expression;
int try_time = 3;
Init();
srand(time(NULL));
while(1)
{
cout<<"*************Guess*************"<<endl;
num_of_leagal_expression = 0;
while( num_of_leagal_expression == 0)
{
num_of_available_number = 0;
for(i=0;i<num_of_used_number;i++)
{
temp = rand()%13+1;
for(j=0;j<num_of_available_number;j++)
if(temp == available_number[j].number)
break;
if(j<num_of_available_number)
available_number[j].appear_time++;
else
{
available_number[j].number = temp;
available_number[j].appear_time = 1;
num_of_available_number++;
}
}
save_or_print = SAVE;
Calculate(0,0);
}
cout<<"Question : ";
for(i=0;i<num_of_available_number;i++)
for(j=0;j<available_number[i].appear_time;j++)
cout<<available_number[i].number<<" ";
cout<<endl;
try_time = 3;
while(try_time--)
{
cout<<"Your answer: ";
cin>>answer;
if(Calculate_Expression(answer,Is_A_Leagal_Expression) == reslut && Is_A_Leagal_Expression == true)
{
cout<<"Right!"<<endl;
break;
}
else
cout<<"Wrong!"<<endl;
}
for(i=0;i<num_of_leagal_expression;i++)
cout<<"Solution #"<<i+1<<" :"<<endl<<leagal_expression[i]<<endl<<endl;
cout<<"continue?(Y/N)"<<endl;
cin>>option;
if(!( strcmp(option,"Y")==0 || strcmp(option,"y")==0 ))
return ;
}
}
void Expression_Imformation::Generate_Expression(char start[],char rule[],int T,int t)
{
int i;
char temp[MAX_LEN];
if(t==T)
{
strcpy(regular_expression[num_of_regular_expression++],start);
return;
}
else
{
for(i=0;start[i]!='\0';i++)
if(start[i]=='E')
{
strcpy(temp,start);
Replace(start,i,rule);
Generate_Expression(start,rule,T,t+1);
strcpy(start,temp);
}
}
}
void Expression_Imformation::Calculate(int num_of_chose_number,int num_of_chose_operator)
{
int i,j,p,counter;
int p_chose_number,p_chose_operator;
char temp[MAX_LEN],int_to_num[MAX_LEN];
bool Is_A_Leagal_Expression;
if(num_of_chose_number == num_of_used_number)
{
if(num_of_chose_operator == (num_of_chose_number - 1))
{
//枚舉所有正則表達式
for(p=0;p<num_of_regular_expression;p++)
{
strcpy(temp,regular_expression[p]);
p_chose_number = p_chose_operator = 0;
// 替換正則表達式中的 E (數字)和 O(操作符)
for(i=0;temp[i]!='\0';i++)
{
if(temp[i]=='E')
{
Replace(temp,i,Num_To_Str(int_to_num,chose_number[p_chose_number]));
i+=strlen(int_to_num);
p_chose_number++;
}
else if(temp[i]=='O')
{
Replace(temp,i,chose_operator[p_chose_operator]);
i+=strlen(chose_operator[p_chose_operator]);
p_chose_operator++;
}
}//for(i)
if(reslut == Calculate_Expression(temp,Is_A_Leagal_Expression))
{
if(save_or_print == PRINT)
cout<<"Soultion #"<<(num_of_leagal_expression+1)<<" : "<<endl<<temp<<endl<<endl;
else
strcpy(leagal_expression[num_of_leagal_expression],temp);
num_of_leagal_expression++;
}
}//for(p)
}
else
{
for(i=0;i<num_of_available_operator;i++)
{
strcpy(chose_operator[num_of_chose_operator],available_operator[i]);
Calculate(num_of_chose_number,num_of_chose_operator+1);
}
}
}
else
{
for(i=0;i<num_of_available_number;i++)
{
counter=0;
for(j=0;j<num_of_chose_number;j++)
if(chose_number[j] == available_number[i].number)
counter++;
if(counter<available_number[i].appear_time)
{
chose_number[num_of_chose_number] = available_number[i].number;
Calculate(num_of_chose_number+1,num_of_chose_operator);
}
}
}
}
// 運算符優先順序
int Expression_Imformation::Precedence(char op)
{
switch(op)
{
case'+':
case'-':
return 1;
case'*':
case'/':return 2;
case'^':return 3;
case'(':
case'@':
default:
return 0;
}
}
// 將字元串 S1 中序表達式轉化成前序表達式
char* Expression_Imformation::Transform(char *S1 ,bool & Is_A_Leagal_Expression)
{
char stack[MAX_LEN];
int stack_top = EMPTY;
char * S2 = new char[strlen(S1)];
int i=0,j=0;
char ch=S1[i];
stack[++stack_top] = '@';
Is_A_Leagal_Expression = true;
while(ch)
{
if(ch==' ') ch=S1[++i];
else if(ch=='(')
{
stack[++stack_top] = ch;
ch=S1[++i];
}
else if(ch==')')
{
while(stack_top!=EMPTY && stack[stack_top]!='(')
S2[j++]=stack[stack_top--];
if(stack_top == EMPTY)
{
Is_A_Leagal_Expression = false;
goto Label;
}
stack_top--;
ch=S1[++i];
}
else if(ch=='+'||ch=='-'||ch=='*'||ch=='/'||ch=='^')
{
if(stack_top == EMPTY)
{
Is_A_Leagal_Expression = false;
goto Label;
}
char w=stack[stack_top];
while(Precedence(w)>=Precedence(ch))
{
S2[j++]=w;
stack_top--;
if(stack_top == EMPTY)
break;
w=stack[stack_top];
}
stack[++stack_top] = ch;
ch=S1[++i];
}
else
{
if((ch<'0'||ch>'9')&&ch!='.')
{
Is_A_Leagal_Expression = false;
goto Label;
}
while((ch>='0'&&ch<='9')||ch=='.')
{
S2[j++]=ch;
ch=S1[++i];
}
S2[j++]=' ';
}
}//end while
if(stack_top == EMPTY)
{
Is_A_Leagal_Expression = false;
goto Label;
}
ch=stack[stack_top--];
while(ch!='@')
{
if(ch=='(')
{
Is_A_Leagal_Expression = false;
goto Label;
}
else
{
S2[j++]=ch;
ch=stack[stack_top--];
}
}
S2[j++]='\0';
strcpy(S1,S2);
Label:
delete []S2;
return S1;
}
// 計算表達式 S1 的值
double Expression_Imformation::Calculate_Expression(char *S1,bool & Is_A_Leagal_Expression )
{
double S[MAX_LEN];
int S_top = EMPTY;
double x,y;
int i=0,k;
Node check[MAX_AVAILABAL_NUMBER_NUM];
int check_p = 0;
char *str = new char [strlen(S1)];
strcpy(str,S1);
Transform(str,Is_A_Leagal_Expression);
if(Is_A_Leagal_Expression == false)
return 0.0;
while(str[i])
{
if(str[i]==' ')
{
i++;
continue;
}
switch(str[i])
{
case '+':
if(S_top<1)
{
Is_A_Leagal_Expression = false;
goto Label;
}
x=S[S_top]+S[S_top-1];
S_top-=2;
i++;
break;
case '-':
if(S_top<1)
{
Is_A_Leagal_Expression = false;
goto Label;
}
x=S[S_top-1] - S[S_top];
S_top-=2;
i++;
break;
case '*':
if(S_top<1)
{
Is_A_Leagal_Expression = false;
goto Label;
}
x=S[S_top-1] * S[S_top];
S_top-=2;
i++;
break;
case '/':
if(S_top<1)
{
Is_A_Leagal_Expression = false;
goto Label;
}
x=S[S_top-1] / S[S_top];
S_top-=2;
i++;
break;
case '^':
if(S_top<1)
{
Is_A_Leagal_Expression = false;
goto Label;
}
x=pow(S[S_top-1],S[S_top]);
S_top-=2;
i++;
break;
default:
x=0;
while(str[i]>='0'&&str[i]<='9')
{
x=x*10+str[i]-'0';
i++;
}
if(str[i]=='.')
{
i++;
y=0;
double j=10.0;
while(str[i]>='0'&&str[i]<='9')
{
y=y+(str[i]-'0')/j;
i++;
j*=10;
}
x+=y;
// 記錄輸入的數字
for(k=0;k<check_p;k++)
if(check[k].number == (int)x)
check[k].appear_time++;
if(k==check_p)
{
check[check_p].number = (int)x;
check[check_p].appear_time =1;
check_p++;
}
}
}//switch
S[++S_top]=x;
}//end while
if(S_top == EMPTY)
{
Is_A_Leagal_Expression = false;
goto Label;
}
// 檢查輸入數字的合法性
for(k=0;k<check_p;k++)
{
for(i=0;i<num_of_available_number;i++)
if(available_number[i].number == check[k].number && available_number[i].appear_time >= check[check_p].appear_time)
break;
if(i==num_of_available_number)
break;
}
if(k < check_p)
{
Is_A_Leagal_Expression = false;
goto Label;
}
x=S[S_top--];
Label:
return x;
}
int main(int argc, char *argv[])
{
class Expression_Imformation game;
// 用戶輸入數字，系統求解（給出全部解）
game.Init_Calculate();
// 系統給出數字，用戶求解（保證有解） 。用戶必須用系統給出的數字求解，最多試3次
game.Init_Guess();
// 給定數據范圍（如1-13）和可使用的操作符（如加減乘除），求出所有解
game.Init_All_Answer();
return 0;
}