表達式求解課程設計
㈠ 《數據結構 課程設計》表達式求值 實驗報告
算術表達式求值演示
一、概述
數據結構課程設計，要求學生在數據結構的邏輯特性和物理表示、數據結構的選擇和應用、演算法的設計及其實現等方面，加深對課程基本內容的理解。同時，在程序設計方法以及上機操作等基本技能和科學作風方面受到比較系統和嚴格的訓練。
在這次的課程設計中我選擇的題目是算術表達式求值演示。表達式計算是實現程序設計語言的基本問題之一，也是棧的應用的一個典型例子。設計一個程序，演示用算符優先法對算術表達式求值的過程。深入了解棧和隊列的特性，以便在解決實際問題中靈活運用它們，同時加深對這種結構的理解和認識。
二、 系統分析
1． 以字元列的形式從終端輸入語法正確的、不含變數的整數表達式。利用已知的算符優先關系，實現對算術四則混合運算表達式的求值，並仿照教科書的例子在求值中運算符棧、運算數棧、輸入字元和主要操作的變化過程。
2． 一般來說，計算機解決一個具體問題時，需要經過幾個步驟：首先要從具體問題抽象出一個適當的數學模型，然後設計一個解決此數學模型的演算法，最後編出程序，進行測試，調試直至得到想要的答案。對於算術表達式這個程序，主要利用棧，把運算的先後步驟進行分析並實現簡單的運算！為實現算符優先演算法，可以使用兩個棧，一個用以寄存運算符，另一個用以寄存操作數和運算結果。
3． 演示程序是以用戶於計算機的對話方式執行，這需要一個模塊來完成使用者與計算機語言的轉化。 4． 程序執行時的命令：
本程序為了使用具體，採用菜單式的方式來完成程序的演示，幾乎不用輸入什麼特殊的命令，只需按提示輸入表達式即可。（要注意輸入時格式，否者可能會引起一些錯誤） 5. 測試數據。
2
算術表達式求值演示
一、概述
數據結構課程設計，要求學生在數據結構的邏輯特性和物理表示、數據結構的選擇和應用、演算法的設計及其實現等方面，加深對課程基本內容的理解。同時，在程序設計方法以及上機操作等基本技能和科學作風方面受到比較系統和嚴格的訓練。
在這次的課程設計中我選擇的題目是算術表達式求值演示。表達式計算是實現程序設計語言的基本問題之一，也是棧的應用的一個典型例子。設計一個程序，演示用算符優先法對算術表達式求值的過程。深入了解棧和隊列的特性，以便在解決實際問題中靈活運用它們，同時加深對這種結構的理解和認識。
二、 系統分析
1． 以字元列的形式從終端輸入語法正確的、不含變數的整數表達式。利用已知的算符優先關系，實現對算術四則混合運算表達式的求值，並仿照教科書的例子在求值中運算符棧、運算數棧、輸入字元和主要操作的變化過程。
2． 一般來說，計算機解決一個具體問題時，需要經過幾個步驟：首先要從具體問題抽象出一個適當的數學模型，然後設計一個解決此數學模型的演算法，最後編出程序，進行測試，調試直至得到想要的答案。對於算術表達式這個程序，主要利用棧，把運算的先後步驟進行分析並實現簡單的運算！為實現算符優先演算法，可以使用兩個棧，一個用以寄存運算符，另一個用以寄存操作數和運算結果。
3． 演示程序是以用戶於計算機的對話方式執行，這需要一個模塊來完成使用者與計算機語言的轉化。 4． 程序執行時的命令：
本程序為了使用具體，採用菜單式的方式來完成程序的演示，幾乎不用輸入什麼特殊的命令，只需按提示輸入表達式即可。（要注意輸入時格式，否者可能會引起一些錯誤） 5. 測試數據。
操作集合：
(1)void InitStack1(SqStack1 &S1);//聲明棧建立函數 (2)void InitStack2(SqStack2 &S2);//聲明棧建立函數
(3)void evaluate(SqStack1 &S1,SqStack2 &S2);//確定如何入棧函數 (4)void Push1(SqStack1 &S1,char e);//聲明入棧函數 (5)void Push2(SqStack2 &S2,float e);//聲明入壓棧函數 (6)char GetTop1(SqStack1 &S1);//聲明取棧頂元素函數 (7)float GetTop2(SqStack2 &S2);//聲明取棧頂元素函數 (8)char Pop1(SqStack1 &S1);//聲明出棧函數 (9)float Pop2(SqStack2 &S2);//聲明出棧函數 (10)char Compare(char m,char n);//聲明比較函數
(11)float Operate(float a,char rheta,float b);//聲明運算函數 (12)void DispStack1(SqStack1 &S1);//從棧底到棧頂依次輸出各元素 (13)void DispStack2(SqStack2 &S2);//從棧底到棧頂依次輸出各元素 }ADT SqStack
結構分析:
棧中的數據節點是通過數組來存儲的。因為在C語言中數組是用下標從零開始的，因此我
們在調用他們的數據是要特別注意。指針變數的值要麼為空(NULL)，不指向任何結點；要麼其值為非空，即它的值是一個結點的存儲地址。注意，當P為空值時，則它不指向任何結點，此時不能通過P來訪問結點，否則會引起程序錯誤。如果輸入的數字不符合題目要求，則會產生錯誤結果。
演算法的時空分析：
時間和空間性能分析：時間上，對於含n個字元的表達式，無論是對其進行合法性檢測還是對其進行入棧出棧操作n次，因此其時間復雜度為O(n)。空間上，由於是用數組來存儲輸入的表達式，用棧來存儲運算中的數據和運算符，而棧的本質也用到的數組，數組在定義時必須確定其大小。在不知表達式長度的情況下確定數組的長度確非易事，此時極易造成空間的浪費，因此空間性能不是很好。
㈡ 數據結構算術表達式求值課程設計
數據結構算術表達式求值課程設計這個真的有。
㈢ 數據結構課程設計：中綴表達式求解，高分求答案！！
要實現原理
還是要程序?
㈣ 急！！！算術表達式的求解（數據結構課程設計）
這個東西，我一時也寫不出來，它主要的思想是中綴表達式轉成後綴表達式，然後後綴表達式求值，這兩部都需要堆棧處理。
㈤ 數據結構課程設計表達式求值的完整程序（在c-free下運行）
思路：中綴表達式－後綴表達式－求值
參考代碼：
#include <iostream>
#include <cstdio>
#include <vector>
#include <cstdlib>
#include <cstring>
#include <iterator>
#include <algorithm>
// 堆棧的數組實現，數組的大小固定。
template<class T>
class stack
{
private:
T *s; // 數組的首地址（棧底）
size_t N; // 指向棧頂第一個空閑塊
const size_t size; // 堆棧的大小，固定不變
public:
stack(size_t n) : size(n)
{
s = new T[n]; // 可能拋出異常
N = 0; // 設置棧頂指針
}
~stack()
{
delete [] s;
}
bool empty() const
{
return N == 0;
}
bool full() const
{
return N == size;
}
void push(const T &object)
{
if (full())
{
throw "error: stack is full !";
}
s[N++] = object;
}
T pop()
{
if (empty())
{
throw "error: stack is empty !";
}
return s[--N];
}
T peek() const
{
if (empty())
{
throw "error: stack is empty !";
}
return s[N-1];
}
friend std::ostream& operator<<(std::ostream& os, const stack<T> &stk)
{
for (size_t i = 0; i < stk.N; i++)
{
std::cout << stk.s[i] << " ";
}
return os;
}
};
// 堆棧的鏈表實現
template<class T>
class STACK
{
private:
typedef struct node
{
T item;
node *next;
node(T x, node *t = NULL) : item(x), next(t) {}
}*link;
link head; // 指向棧頂第一個有效對象
public:
STACK(size_t n)
{
head = NULL;
}
~STACK() // 也可以用pop的方法刪除，但效率低
{
link t = head;
while (t != NULL)
{
link d = t;
t = t->next;
delete d;
}
}
bool empty() const
{
return head == NULL;
}
bool full() const
{
return false;
}
void push(const T &object)
{
head = new node(object, head);
}
T pop()
{
if (empty())
{
throw "error: stack is empty !";
}
T v = head->item;
link t = head->next;
delete head;
head = t;
return v;
}
T peek() const
{
if (empty())
{
throw "error: stack is empty !";
}
return head->item;
}
friend std::ostream& operator<<(std::ostream& os, const STACK<T> &stk)
{
for (link t = stk.head; t != NULL; t = t->next)
{
std::cout << t->item << " ";
}
return os;
}
};
// 中綴表達式轉化為後綴表達式，僅支持加減乘除運算、操作數為1位十進制非負整數的表達式。
char* infix2postfix(const char *infix, char *postfix)
{
const size_t N = strlen(infix);
if (N == 0 || postfix == NULL)
{
return postfix;
}
stack<char> opcode(N); // 堆棧存放的是操作符
for (size_t i = 0; i < N; i++)
{
switch (infix[i])
{
case '(': // 直接忽略左括弧
break;
case ')': // 彈出操作符
*postfix++ = opcode.pop();
*postfix++ = ' ';
break;
case '+':
case '-':
case '*':
case '/':
opcode.push(infix[i]); // 壓入操作符
break;
default:
if (isdigit(infix[i])) // 如果是數字，直接輸出
{
*postfix++ = infix[i];
*postfix++ = ' ';
}
}
}
return postfix;
}
// 後綴表達式轉化為中綴表達式，僅支持加減乘除運算、操作數為1位十進制非負整數的表達式。
char* postfix2infix(const char *postfix, char *infix)
{
const size_t N = strlen(postfix);
if (N == 0 || infix == NULL)
{
return infix;
}
*infix = '\0'; // 初始化輸出字元串為空串
std::vector<std::string> v;
// 初始化，將所有有效字元放入容器
for (size_t i = 0; i < N; i++)
{
if (isdigit(postfix[i]) || postfix[i] == '+'
|| postfix[i] == '-' || postfix[i] == '*' || postfix[i] == '/')
{
v.push_back(std::string(1, postfix[i]));
}
}
// 處理每一個操作符
for (std::vector<std::string>::iterator b = v.begin(); b < v.end(); b++)
{
if (*b == "+" || *b == "-" || *b == "*" || *b == "/")
{
(v.begin(), v.end(), std::ostream_iterator<std::string>(std::cout, "\n"));
std::cout << "------------------------------------------------" << std::endl;
std::string opcode = *(b);
std::string oprand1 = *(b - 2);
std::string oprand2 = *(b - 1);
b = v.erase(b - 2, b + 1); // 刪除原來的三個表達式，用一個新的表達式替換
b = v.insert(b, std::string("(") + oprand1 + opcode + oprand2 + std::string(")"));
}
}
for (std::vector<std::string>::iterator b = v.begin(); b < v.end(); b++)
{
strcat(infix, (*b).c_str());
}
return infix;
}
// 計算後綴表達式的值，僅支持加減乘除運算、操作數為非負整數的表達式。
int postfix_eval(const char * postfix)
{
const size_t N = strlen(postfix);
if (N == 0)
{
return 0;
}
STACK<int> operand(N); // 堆棧存放的是操作數
for (size_t i = 0 ; i < N; i++)
{
switch (postfix[i])
{
int op1, op2;
case '+':
op1 = operand.pop();
op2 = operand.pop();
operand.push(op1 + op2);
break;
case '-':
op1 = operand.pop();
op2 = operand.pop();
operand.push(op1 - op2);
break;
case '*':
op1 = operand.pop();
op2 = operand.pop();
operand.push(op1 * op2);
break;
case '/':
op1 = operand.pop();
op2 = operand.pop();
operand.push(op1 / op2);
break;
default:
if (isdigit(postfix[i])) // 執行類似atoi()的功能
{
operand.push(0);
while (isdigit(postfix[i]))
{
operand.push(10 * operand.pop() + postfix[i++] - '0');
}
i--;
}
}
std::cout << operand << std::endl; // 輸出堆棧的內容
}
return operand.pop();
}
// 本程序演示了如何後綴表達式和中綴表達式的相互轉換，並利用堆棧計算後綴表達式。
// 轉換方向：org_infix --> postfix --> infix
int main(int argc, const char *argv[])
{
// const char *org_infix = "(5*(((9+8)*(4*6))+7))"; // section 4.3
const char *org_infix = "(5*((9*8)+(7*(4+6))))"; // exercise 4.12
std::cout << "原始中綴表達式：" << org_infix << std::endl;
char *const postfix = new char[strlen(org_infix) + 1];
infix2postfix(org_infix, postfix);
std::cout << "後綴表達式：" << postfix << std::endl;
char *const infix = new char[strlen(postfix) + 1];
postfix2infix(postfix, infix);
std::cout << "中綴表達式：" << infix << std::endl;
std::cout << "計算結果是：" << postfix_eval(postfix) << std::endl;
std::cout << "計算結果是：" << postfix_eval("5 9*8 7 4 6+*2 1 3 * + * + *") << std::endl; // exercise 4.13
delete []infix;
delete []postfix;
return 0;
}
㈥ 數據結構課程設計 表達式求解問題 求一C程序
呵呵 自己做吧 能學到很多東西 我以前就是自己做的 別偷懶哦
㈦ 代碼報錯 算術表達式求解 （要求顯示計算步驟）課程設計
undeclared identifier 是沒有聲明相抄關變數
redefinition; different type modifiers 是重復定義了相關變數
根據報錯的變數去找到對應的位置,看看在變數作用域范圍裡面有沒有正確定義
㈧ 表達式求值問題課程設計報告c++
想做私信我
㈨ 基於順序棧的簡單算起術表達式求值課程設計
設計一個程序，演示用算符優先法對算術表達式求值的過程。
利用算符優先關系，實專現對算術四則混合運算屬表達式的求值。 （1）輸入的形式：表達式，例如2*(3+4) 包含的運算符只能有'+' 、'-' 、'*' 、'/' 、'('、 ')'； （2）輸出的形式：運算結果，