數據結構課程設計算術表達式求值
⑴ 數據結構c語言 算術表達式求值
逆波蘭堆棧操作
⑵ 數據結構算術表達式求值課程設計
思路：中綴表達式－後綴表達式－求值參考代碼：#include#include#include#include#include#include#include//堆棧的數組實現，數組的大小固定。templateclassstack{private:T*s;//數組的首地址（棧底）size_tN;//指向棧頂第一個空閑塊constsize_tsize;//堆棧的大小，固定不變public:stack(size_tn):size(n){s=newT[n];//可能拋出異常N=0;//設置棧頂指針}~stack(){delete[]s;}boolempty()const{returnN==0;}boolfull()const{returnN==size;}voidpush(constT&object){if(full()){throw"error:stackisfull!";}s[N++]=object;}Tpop(){if(empty()){throw"error:stackisempty!";}returns[--N];}Tpeek()const{if(empty()){throw"error:stackisempty!";}returns[N-1];}friendstd::ostream&operator&stk){for(size_ti=0;iclassSTACK{private:typedefstructnode{Titem;node*next;node(Tx,node*t=NULL):item(x),next(t){}}*link;linkhead;//指向棧頂第一個有效對象public:STACK(size_tn){head=NULL;}~STACK()//也可以用pop的方法刪除，但效率低{linkt=head;while(t!=NULL){linkd=t;t=t->next;deleted;}}boolempty()const{returnhead==NULL;}boolfull()const{returnfalse;}voidpush(constT&object){head=newnode(object,head);}Tpop(){if(empty()){throw"error:stackisempty!";}Tv=head->item;linkt=head->next;deletehead;head=t;returnv;}Tpeek()const{if(empty()){throw"error:stackisempty!";}returnhead->item;}friendstd::ostream&operator&stk){for(linkt=stk.head;t!=NULL;t=t->next){std::coutitemopcode(N);//堆棧存放的是操作符for(size_ti=0;iv;//初始化，將所有有效字元放入容器for(size_ti=0;i::iteratorb=v.begin();b(std::cout,"\n"));std::cout::iteratorb=v.begin();boperand(N);//堆棧存放的是操作數for(size_ti=0;ipostfix-->infixintmain(intargc,constchar*argv[]){//constchar*org_infix="(5*(((9+8)*(4*6))+7))";//section4.3constchar*org_infix="(5*((9*8)+(7*(4+6))))";//exercise4.12std::cout<<"原始中綴表達式："<
⑶ 數據結構課程設計算術表達式求值
怎麼沒有表達式？？
⑷ 求《數據結構》課程設計（題目：算術表達式求值）
如果嫌一個題目涉及的內容太少
可以採用題目組的方式
如：表達式和迷宮一組
各種排序方法一組
最優二叉樹圖的計算遍歷
棧與廣義表
等等
可以分組來讓學生選擇。
說實話找個好題目真的好難~~~
而且抄襲現象嚴重~~~
最後拿到手的基本是一個代碼
有幾個給你變變形
那就是好學生~~~
網上有大量的例題，可以下來
改改數
或者敘述
在組合成沒有重復的題組，一人一個組
不重復
題也不重復~
這樣就可以了
但在事前一定要和學生講好
怎麼出題，要不。。。。。。沒幾個能過的~~~
還有難免有人會說你變態~~其實為他們好
以後他們會知道的~
-----------------------------------
剛才看別人的問題才想起來
你完全可以用
ACM
的競賽題。
估計50個里頭能有3個做出來吧~~
怎麼樣？
⑸ 數據結構課程設計報告表達式求值
數據結構，課程設計
報告的表達，我知道怎麼做
成
⑹ 數據結構之算術表達式求值
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <conio.h>
#define TRUE 1
#define FALSE 0
#define Stack_Size 50
char ops[7]={'+','-','*','/','(',')','#'}; /*運算符數組*/
int cmp[7][7]={{2,2,1,1,1,2,2}, /*用來進行比較運算符優先順序的矩陣,3代表'=',2代表'>',1代表'<',0代表不可比*/
{2,2,1,1,1,2,2},
{2,2,2,2,1,2,2},
{2,2,2,2,1,2,2},
{1,1,1,1,1,3,0},
{2,2,2,2,0,2,2},
{1,1,1,1,1,0,3}};
typedef struct
{
char elem[Stack_Size];
int top;
}SeqStack; /*運算符棧的定義*/
typedef struct
{
int elem[Stack_Size];
int top;
}nSeqStack; /* 運算數棧的定義*/
void InitStack(SeqStack *S) /*初始化運算符棧*/
{
S->top =-1;
}
void InitStackn(nSeqStack *S) /*初始化運算數棧*/
{
S->top =-1;
}
int IsEmpty(SeqStack *S) /*判斷棧S為空棧時返回值為真，反之為假*/
{
return(S->top==-1?TRUE:FALSE);
}
int IsEmptyn(nSeqStack *S) /*判斷棧S為空棧時返回值為真，反之為假*/
{
return(S->top==-1?TRUE:FALSE);
}
/*判棧滿*/
int IsFull(SeqStack *S) /*判斷棧S為滿棧時返回值為真，反之為假*/
{
return(S->top==Stack_Size-1?TRUE:FALSE);
}
int IsFulln(nSeqStack *S) /*判斷棧S為滿棧時返回值為真，反之為假*/
{
return(S->top==Stack_Size-1?TRUE:FALSE);
}
int Push(SeqStack *S, char x) /*運算符棧入棧函數*/
{
if (S->top==Stack_Size-1)
{
printf("Stack is full!\n");
return FALSE;
}
else
{
S->top++;
S->elem[S->top]=x;
return TRUE;
}
}
int Pushn(nSeqStack *S, int x) /*運算數棧入棧函數*/
{
if (S->top==Stack_Size-1)
{
printf("Stack is full!\n");
return FALSE;
}
else
{
S->top++;
S->elem[S->top]=x;
return TRUE;
}
}
int Pop(SeqStack *S, char *x) /*運算符棧出棧函數*/
{
if (S->top==-1)
{
printf("運算符棧空!\n");
return FALSE;
}
else
{
*x=S->elem[S->top];
S->top--;
return TRUE;
}
}
int Popn(nSeqStack *S, int *x) /*運算數棧出棧函數*/
{
if (S->top==-1)
{
printf("運算符棧空!\n");
return FALSE;
}
else
{
*x=S->elem[S->top];
S->top--;
return TRUE;
}
}
char GetTop(SeqStack *S) /*運算符棧取棧頂元素函數*/
{
if (S->top ==-1)
{
printf("運算符棧為空!\n");
return FALSE;
}
else
{
return (S->elem[S->top]);
}
}
int GetTopn(nSeqStack *S) /*運算數棧取棧頂元素函數*/
{
if (S->top ==-1)
{
printf("運算符棧為空!\n");
return FALSE;
}
else
{
return (S->elem[S->top]);
}
}
int Isoperator(char ch) /*判斷輸入字元是否為運算符函數,是返回TRUE,不是返回FALSE*/
{
int i;
for (i=0;i<7;i++)
{
if(ch==ops[i])
return TRUE;
}
return FALSE;
}
/*
int isvariable(char ch)
{ if (ch>='a'&&ch<='z')
return true;
else
return false;
}*/
char Compare(char ch1, char ch2) /*比較運算符優先順序函數*/
{
int i,m,n;
char pri; /*保存優先順序比較後的結果'>'、'<'、'='*/
int priority; /*優先順序比較矩陣中的結果*/
for(i=0;i<7;i++) /*找到相比較的兩個運算符在比較矩陣里的相對位置*/
{
if(ch1==ops[i])
m=i;
if (ch2==ops[i])
n=i;
}
priority = cmp[m][n];
switch(priority)
{
case 1:
pri='<';
break;
case 2:
pri='>';
break;
case 3:
pri='=';
break;
case 0:
pri='$';
printf("表達式錯誤!\n");
break;
}
return pri;
}
int Execute(int a, char op, int b) /*運算函數*/
{
int result;
switch(op)
{
case '+':
result=a+b;
break;
case '-':
result=a-b;
break;
case '*':
result=a*b;
break;
case '/':
result=a/b;
break;
}
return result;
}
int ExpEvaluation()
/*讀入一個簡單算術表達式並計算其值。optr和operand分別為運算符棧和運算數棧，OPS為運算符集合*/
{
int a,b,v,temp;
char ch,op;
char *str;
int i=0;
SeqStack optr; /*運算符棧*/
nSeqStack operand; /*運算數棧*/
InitStack(&optr);
InitStackn(&operand);
Push(&optr,'#');
printf("請輸入表達式(以#結束):\n"); /*表達式輸入*/
str =(char *)malloc(50*sizeof(char));
gets(str); /*取得一行表達式至字元串中*/
ch=str[i];
i++;
while(ch!='#'||GetTop(&optr)!='#')
{
if(!Isoperator(ch))
{
temp=ch-'0'; /*將字元轉換為十進制數*/
ch=str[i];
i++;
while(!Isoperator(ch))
{
temp=temp*10 + ch-'0'; /*將逐個讀入運算數的各位轉化為十進制數*/
ch=str[i];
i++;
}
Pushn(&operand,temp);
}
else
{
switch(Compare(GetTop(&optr),ch))
{
case '<':
Push(&optr,ch);
ch=str[i];
i++;
break;
case '=':
Pop(&optr,&op);
ch=str[i];
i++;
break;
case '>':
Pop(&optr,&op);
Popn(&operand,&b);
Popn(&operand,&a);
v=Execute(a,op,b); /* 對a和b進行op運算 */
Pushn(&operand,v);
break;
}
}
}
v=GetTopn(&operand);
return v;
}
void main() /*主函數*/
{
int result;
result=ExpEvaluation();
printf("\n表達式結果是%d\n",result);
}
⑺ 數據結構課程設計之利用棧求表達式的值
需要使用「棧」這種數據結構吧，可以看一下教材，有介紹演算法，可以根據版演算法寫權出代碼，需要使用兩個工作棧，一個稱作OPTR，用以寄存運算符；另一個稱作OPND，用以寄存操作數或運算結果。演算法的基本思想是：一，置操作數棧為空棧，表達式起始符「#」為運算符棧的棧底元素。二，依次讀入表達式中每個字元，若是操作數則進OPND棧，若是運算符則和OPTR棧的棧頂運算符比較優先權後作相應操作，直至整個表達式求值完畢（即OPTR棧的棧頂元素和當前讀入字元均為「#」）。
⑻ 數據結構課程設計表達式求值的完整程序（在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;
}