當前位置:首頁 » 編程語言 » 課程設計表達式求值c語言
擴展閱讀
webinf下怎麼引入js 2023-08-31 21:54:13
堡壘機怎麼打開web 2023-08-31 21:54:11

課程設計表達式求值c語言

發布時間: 2022-05-24 15:24:51

① 編寫程序對表達式求值c語言,該如何處理

先讀取輸入表達式,轉為前綴或者後綴形式。
然後再處理轉換後的表達式進行求值。
這個是很常見的一個數據結構題目,網上有很多參考代碼的。

② C語言 任意表達式求值。(棧的應用

/*** 只適合整數的表達式求值 ***/
/***其中部分可作修改,表達式也可是輸入的***/
#include "iostream.h"
const int n0=30;
int s1[n0+1]; //操作數棧
char s2[n0+1]; //運算符棧
int t1,t2;
int num[4]; //提取表達式中的整數

void calcu() //一次計算
{
int x1,x2,x;
char p;
//彈出一個運算符
p=s2[t2--];
//彈出兩個操作數
x2=s1[t1--];
x1=s1[t1--];
//進行一次運算
switch(p) {
case '+':x=x1+x2;break;
case '-':x=x1-x2;break;
case '*':x=x1*x2;break;
case '/':x=x1/x2;
}
//結果壓入操作數棧
s1[++t1]=x;
}

int calculator(char *f)
{
int v,i=0;
char *p=f;
t1=t2=0; //設置空棧
while (*p!='\0')
switch(*p) {
case '+': case '-':
while (t2&&(s2[t2]!='('))
//執行先遇到的加、減、乘、除運算
calcu();
//當前運算符進棧
s2[++t2]=*p;
//讀下一個字元
p++;
break;
case '*': case '/':
if (t2&&(s2[t2]=='*')||(s2[t2]=='/'))
//執行先遇到的乘、除運算
calcu();
//當前運算符進棧
s2[++t2]=*p;
//讀下一個字元
p++;
break;
case '(':
//左括弧進棧
s2[++t2]=*p;
//讀下一個字元
p++;
break;
case ')':
while (s2[t2]!='(')
//執行括弧內的加、減、乘、除運算
calcu();
//彈出左括弧
t2--;
//讀下一個字元
p++;
break;
default:
//把字元串轉換成整數值
v=0;
do {
v=10*v+*p-'0';
p++;
} while((*p>='0')&&(*p<='9'));
//操作數進棧
s1[++t1]=v;
num[i++]=v;
};
//執行先遇到的加、減、乘、除運算
while (t2) calcu();
//返回結果
return s1[t1];
}

void main()
{
char a[]="5*(40+6)-39";
cout<<calculator(a)<<endl;
cout<<"其中的數字為:\n";
for (int i=0;i<4;i++)
{
cout<<num[i]<<' ';
}
cout<<endl;
}
原來做過的東西,是C++的,VC++6.0環境下調試運行成功。

③ C語言表達式求值

//表達式求值
//By:jimly
//10/10/2009
//例如:輸入2+2(4-6*3)=
//以"="結束,然後回車即出結果
#include <stdio.h>
#include <conio.h>
#include <windows.h>
#include <assert.h>
typedef float ElemType;
typedef struct Stack
{
ElemType *base; // 棧基址
ElemType *top; // 棧頂
int stacksize; // 棧存儲空間的尺寸
} SqStack;
/*------------------------------------------------------------
// 棧的基本操作
------------------------------------------------------------*/
bool InitStack(SqStack *S);
bool InitStack(SqStack *S);
void DestroyStack(SqStack *S);
bool StackEmpty(SqStack S);
int StackLength(SqStack S);
ElemType GetTop(SqStack S, ElemType *e);
void StackTraverse(SqStack S, void (*fp)(ElemType));
bool Push(SqStack *S, ElemType e);
bool Pop(SqStack *S, ElemType *e);
/*------------------------------------------------------------
// 表達式求值的操作函數定義
------------------------------------------------------------*/
char Precede(char A1,char A2);
ElemType Operate(ElemType a,ElemType theta,ElemType b);
bool In(char c,char op[]);
ElemType EvaluateExpression();
void Menu();//////////////////////////////////////////////
// Eval_exdivssion.cpp 表達式求值實現函數 //
//////////////////////////////////////////////
/*------------------------------------------------------------
操作目的: 判定運算符棧的棧頂運算符A1和讀入的運算符A2之間優先關系的函數
初始條件: 無
操作結果: 判斷出優先關系
函數參數:
char A1 運算符
char A2 運算符
返回值:
char 大小關系
------------------------------------------------------------*/
char Precede(char A1,char A2)
{
if (A1 == '+' || A1 == '-')
{
if (A2 == '+' || A2 == '-' || A2 == ')' || A2 == '=')
{
return '>';
}
else
return '<';
}
if (A1 == '*' || A1 == '/')
{
if (A2 == '(')
{
return '<';
}
else
return '>';
}
if (A1 == '(')
{
if (A2 == ')')
{
return '=';
}
if (A2 == '=')
{
return 'E';
}
else
return '<';
}
if (A1 == ')')
{
if (A2 == '(')
{
return 'E';
}
if (A2 == '=')
{
return 'E';
}
else
return '>';
}
if (A1 == '=')
{
if (A2 == '=')
{
return '=';
}
else
return '<';
}
else
return '=';
}
/*------------------------------------------------------------
操作目的: 二元運算a與b的函數
初始條件: 無
操作結果: 返回運算結果
函數參數:
ElemType a 操作數
ElemType theta 操作符
ElemType b 操作數
返回值:
ElemType 運算結果
------------------------------------------------------------*/
ElemType Operate(ElemType a,ElemType theta,ElemType b)
{
switch(char(theta))
{
case '+':
return a += b;
break;
case '-':
return a -= b;
break;
case '*':
return a *= b;
break;
case '/':
if(b==0)
{
printf("除數不能為0!!\n");
exit(0);
}
return a /= b;
break;
} return 0;
}
/*------------------------------------------------------------
操作目的: 判斷字元c是否屬於運算符集合op
初始條件: 無
操作結果: 返回判斷結果
函數參數:
char c 要判斷的字元
char op[] 運算符集合
返回值:
bool 屬於返回true 否則返回false
------------------------------------------------------------*/
bool In(char c,char op[])
{
for (int i = 0;i<7;i++)
{
if (op[i] == c)
return true;
}
return false;
}
/*------------------------------------------------------------
操作目的: 算術表達式求值的運算符優先演算法
初始條件: 無
操作結果: 返回表達式的值
函數參數:

返回值:
ElemType 運算結果
------------------------------------------------------------*/
ElemType EvaluateExpression()
{
SqStack OPTR; //運算符棧
SqStack OPND; //運算數棧
char Ct = '='; //判斷是否結束的標識
int i = 0,j = 1;
ElemType e = 0,t = 0,c;
char op[7] = {'+','-','*','/','(',')','='}; InitStack(&OPTR); //初始化
Push(&OPTR,Ct);
InitStack(&OPND); //初始化 c = (float)getchar();
while (c!='=' || GetTop(OPTR,&e)!='=')
{
if (!In((char)c,op)) //不是運算e符進棧
{
while(!In((char)c,op)) //可以是幾位數
{
t = t*10+(c-48);
c = (float)getchar();
}
Push(&OPND,t);
t = 0;
} else
{
switch (Precede((char)GetTop(OPTR,&e),(char)c))
{
case '<'://棧頂元素優先權低
Push(&OPTR,c);
c = (float)getchar();
break;
case '='://脫括弧並接受下個字元
ElemType x;
Pop(&OPTR,&x);
c = (float)getchar();
break;
case '>'://退棧並將運算結果入棧
ElemType b,theta,a;
Pop(&OPTR,&theta);
Pop(&OPND,&b);
Pop(&OPND,&a);
Push(&OPND,Operate(a,theta,b));
break;
case 'E':
printf("括弧不匹配!!\n");
exit(0);
break;

}
}
}
ElemType tem = GetTop(OPND,&e);
DestroyStack(&OPND);
DestroyStack(&OPTR);
return tem;
}/***
*DynaSeqStack.cpp - 動態順序棧,即棧的動態順序存儲實現
****/
const int STACK_INIT_SIZE = 100; // 初始分配的長度
const int STACKINCREMENT = 10; // 分配內存的增量
/*------------------------------------------------------------
操作目的: 初始化棧
初始條件: 無
操作結果: 構造一個空的棧
函數參數:
SqStack *S 待初始化的棧
返回值:
bool 操作是否成功
------------------------------------------------------------*/
bool InitStack(SqStack *S)
{
assert(S != NULL);
S->base = (ElemType *)malloc(sizeof(ElemType) * STACK_INIT_SIZE);

if(S->base == NULL) return false; S->top = S->base;
S->stacksize = STACK_INIT_SIZE; return true;
}/*------------------------------------------------------------
操作目的: 銷毀棧
初始條件: 棧S已存在
操作結果: 銷毀棧S
函數參數:
SqStack *S 待銷毀的棧
返回值:

------------------------------------------------------------*/
void DestroyStack(SqStack *S)
{
assert(S != NULL); free(S->base);
S->top = S->base = NULL;
}/*------------------------------------------------------------
操作目的: 判斷棧是否為空
初始條件: 棧S已存在
操作結果: 若S為空棧,則返回true,否則返回false
函數參數:
SqStack S 待判斷的棧
返回值:
bool 是否為空
------------------------------------------------------------*/
bool StackEmpty(SqStack S)
{
assert((S.base != NULL) && (S.top != NULL));
return(S.base == S.top);
}/*------------------------------------------------------------
操作目的: 得到棧的長度
初始條件: 棧S已存在
操作結果: 返回S中數據元素的個數
函數參數:
SqStack S 棧S
返回值:
int 數據元素的個數
------------------------------------------------------------*/
int StackLength(SqStack S)
{
assert((S.base != NULL) && (S.top != NULL));
return(S.top-S.base);
}/*------------------------------------------------------------
操作目的: 得到棧頂元素
初始條件: 棧S已存在
操作結果: 用e返回棧頂元素
函數參數:
SqStack S 棧S
ElemType *e 棧頂元素的值
返回值:
bool 操作是否成功
------------------------------------------------------------*/
ElemType GetTop(SqStack S, ElemType *e)
{
assert((S.base != NULL) && (S.top != NULL));
if(StackEmpty(S)) return false; *e = *(S.top-1);
return *e;
}/*------------------------------------------------------------
操作目的: 遍歷棧
初始條件: 棧S已存在
操作結果: 依次對S的每個元素調用函數fp
函數參數:
SqStack S 棧S
void (*fp)() 訪問每個數據元素的函數指針
返回值:

------------------------------------------------------------*/
void StackTraverse(SqStack S, void (*fp)(ElemType))
{
assert((S.base != NULL) && (S.top != NULL));
for(; S.base<S.top; S.base++) (*fp)(*S.base);
}/*------------------------------------------------------------
操作目的: 壓棧——插入元素e為新的棧頂元素
初始條件: 棧S已存在
操作結果: 插入數據元素e作為新的棧頂
函數參數:
SqStack *S 棧S
ElemType e 待插入的數據元素
返回值:
bool 操作是否成功
------------------------------------------------------------*/
bool Push(SqStack *S, ElemType e)
{
if (S->top - S->base>=S->stacksize)
{
S->base = (ElemType *)realloc(S->base,(S->stacksize + STACKINCREMENT) * sizeof(ElemType));
if (!S->base)
exit(0);
S->top = S->base + S->stacksize;
S->stacksize += STACKINCREMENT;
}
*S->top++ = e; return true;
}/*------------------------------------------------------------
操作目的: 彈棧——刪除棧頂元素
初始條件: 棧S已存在且非空
操作結果: 刪除S的棧頂元素,並用e返回其值
函數參數:
SqStack *S 棧S
ElemType *e 被刪除的數據元素值
返回值:
bool 操作是否成功
------------------------------------------------------------*/
bool Pop(SqStack *S, ElemType *e)
{
if(S == NULL) return false;
assert((S->base != NULL) && (S->top != NULL));
if(StackEmpty(*S)) return false; *e = *(--S->top);
return true;
}//////菜單///////
void Menu()
{
printf("表達式求值模擬程序\n\n");

printf("功能菜單:\n");
printf("==============\n");
printf("[1] 輸入表達式並求值\n");
printf("[0] 退出 \n");
printf("==============\n");
printf("請輸入你的選擇(0~1)(以回車結束):");
}///////// 主函數 ///////////
//////////////////////////////
int main()
{
char ch = ' ',tp; do
{
system("cls");
Menu();
ch = getchar();
if (ch == '0')
break;
tp = getchar();
printf("請輸入一個表達式(最後輸入」=「,然後回車出結果):");
printf("這個表達式結果為:%g\n",EvaluateExpression());
tp = getchar();
printf("任意鍵繼續...");
getch();
} while (true); return 0;
}//end

④ c語言表達式求值

#include"stdio.h"
#include"malloc.h"
#include"math.h"
#include"stdlib.h"
#define ERROR 0
#define OK 1
#define OVERFLOW -2
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10

typedef int Status;
typedef char SElemType;
typedef char OpeandType;

typedef struct
{
SElemType *base;
SElemType *top;
int stacksize;

}SqStack;

Status InitStack (SqStack &S);

char GetTop(SqStack S);

Status Push(SqStack &S,SElemType e);

Status Pop(SqStack &S,SElemType &e);

char Precede(char t,char c);

int In(char c);

int Operate(SElemType a,SElemType theta,SElemType b);//

OpeandType EvaluateExpression();

Status InitStack (SqStack &S)
{
//構造一個空棧
S.base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType));
if(!S.base)exit(OVERFLOW);
S.top=S.base;
S.stacksize=STACK_INIT_SIZE;
return OK;
}//InitStatus

char GetTop(SqStack S)
{
//若棧不為空,則用e返回s的棧頂元素,並返回OK;否則返回ERROR
SElemType e;
if(S.top==S.base)return ERROR;
e=*(S.top-1);
S.top =S.top +1;
return e;
}//GetTop

Status Push(SqStack &S,SElemType e)
{
//插入元素e為新的棧頂元素
if((S.top-S.base)>=S.stacksize)
{
//棧滿,追加存儲空間
S.base=(SElemType *)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType));
if(!S.base)
exit(OVERFLOW);//存儲分配失敗
S.top=S.base+S.stacksize;
S.stacksize+=STACKINCREMENT;
}
*S.top++=e;//
return OK;
}//Push

Status Pop(SqStack &S,SElemType &e)
{
//若棧不為空,則刪除s的棧頂元素,用e返回其值,並返回OK;否則返回ERROR
if(S.top==S.base)return ERROR;
e=*(--S.top);
return OK;

}//Pop

char Precede(char t,char c)
{
switch(c)
{
case '+':
if(t=='+'||t=='-'||t=='*'||t=='/'||t==')')
return '>';
else
return'<';
break;
case '-':
if(t=='+'||t=='-'||t=='*'||t=='/'||t==')')
return '>';
else
return '<';
break;
case '*':
if(t=='*'||t=='/')
return '>';
else
return '<';
break;
case '/':
if(t=='*'||t=='/')
return '>';
else
return '<';
break;
case '(':
return '<';
break;
case ')':
if(t=='(')
return '=';
else
return '>';
break;
case '#':
if(t=='#')
return '=';
else
return '>';
break;
}
return 'h';
}//Precede

int In(char c)
{
switch(c)
{
case '+':
case '-':
case '*':
case '/':
case '(':
case ')':
case '#':
return OK;
break;
}
return 0;//
}//判斷c是否為運算符,是則返回1,否則返回0

int Operate(SElemType a,SElemType theta,SElemType b)//
{
int x,y;
x=a-'0';
y=b-'0';
switch(theta)
{
case '-':return x-y;
case '*':return x*y;
case '/':
if(y==0)
return 0;
return x/y;
case '+':return x+y;
default :return 0;
}
}
OpeandType EvaluateExpression()
{
//算術表達式求值的算符優先法。設OPTR和OPND分別為算符棧和運算數棧,
//OP為運算符集合。
SqStack OPTR,OPND;
SElemType e;
int k;//
SElemType t;
//int kk=0;
SElemType theta,a,b,f;
InitStack(OPTR);
Push(OPTR,'#');
InitStack(OPND);
SElemType c;//
c=getchar();

while(c != '#'||(GetTop(OPTR))!='#')
{
if(!In(c))
{//不是運算符者進棧
Push(OPND,c);
c=getchar();
}
else
{
switch(Precede(GetTop(OPTR),c))
{
case '<'://棧頂元素優先權低
Push(OPTR,c);

c=getchar();//
break;
case '='://脫括弧並接收下一個字元
Pop(OPTR,t);
c=getchar();//
break;
case'>'://退棧並將運算結果入棧
Pop(OPTR,theta);
Pop(OPND,b);
Pop(OPND,a);
k=Operate(a,theta,b);//

f=k+'0';//
Push(OPND,f);//

break;
}//switch
}
}///while
e=GetTop(OPND);

if(!e)
return 'k';
return e;
//printf("endl");
}
void main()
{
char sum;
printf("請輸入你要運算的表達式(以『#』號鍵結束):");
sum=EvaluateExpression();
printf("運算結果是:%c\n",sum);
}
可以運行10 以內的,結果超過10就不行了,中途也是,如果要超過10的話,再說

⑤ C語言關於表達式求值

c語言有豐富的表達式,這是它的特點之一,表達式主要有4類,算術表達式,賦值表達式,逗號表達式,關系表達式
1.算術表達式就是包含算術運算符(如+
-
/
*
%等)的表達式(不是語句,後面沒有分號),如:a+b
,a%b,a+b-c*d,3+5等,算術表達式的值就是最後算出的結果,如3+5這個表達式的值就是8
2.賦值表達式,就是含有賦值運算符=的表達式,如a=5,b=3,c='a'等,=左邊的a,b,c稱為左值,必須為變數,=右邊的5,3,'a'稱為右值,必須為常量,賦值表達式的值為右值,如a=3的值為3,c='a'的值為字母a的ascii碼65(當然也可以認為它的值就是字母a)
3.逗號表達式就是含有逗號的表達式,形式:表達式1,表達式2,表達式3.......如a,b,c
3,5,7
a=3,b=4,c=6
3,a=5,b=6等
逗號表達式的值為,最右邊的表達式的值,如3,4,5的值就是5,表達式a=3,b=4,c=6的值就是表達式b=6的值,由上述分析知,表達式b=6的值就是6,所以表達式a=3,b=4,c=6的值就是6
4.關系表達式,指含有關系運算符(如>
<
>=
==
=<等)的表達式(其實也是算術表達式的一種)如a>b,a>6,6>5,3<2,4==6等,如果表達式的關系是正確的,那麼表達式的值為1,否則為0
如6>5正確,表達式的值為1,3<2,和4==6錯誤,表達式的值為0
當然可以細分為很多種表達式,不過主要也就是這幾種的變型,希望對你有所幫助

⑥ c語言:表達式求值實現

#include"stdio.h"
#include"malloc.h"

#defineTRUE1
#defineFALSE0
#defineOK1
#defineERROR0
#defineINFEASIBLE-1
#defineOVERFLOW-2

typedefintStatus;
#defineSTACK_INIT_SIZE100
#defineSTACKINCREMENT10

typedefstruct{
SElemType*base;
SElemType*top;
intstacksize;
}SqStack;
//構造一個空棧
StatusInitStack(SqStack*S){
S->base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType));

if(!S->base)
exit(OVERFLOW);
S->top=S->base;
S->stacksize=STACK_INIT_SIZE;
returnOK;
}
//判斷是否為空棧
StatusStackEmpty(SqStackS){
if(S.top==S.base)
returnTRUE;
else
returnFALSE;
}
//用e返回S的頂元素
StatusGetTop(SqStackS,SElemType*e){
if(S.top==S.base)
returnERROR;
*e=*(S.top-1);
returnOK;
}
//插入e為新的頂元素
StatusPush(SqStack*S,SElemTypee){
if((S->top-S->base)>=S->stacksize){
S->base=(
SElemType*)realloc(S->base,
(S->stacksize+STACKINCREMENT)*sizeof(SElemType)
);
if(!S->base)
exit(OVERFLOW);
S->top=S->base+S->stacksize;
S->stacksize+=STACKINCREMENT;
}
*(S->top)=e;
S->top++;
returnOK;
}
//刪除S的頂元素,並用e返回其值
StatusPop(SqStack*S,SElemType*e){
if(S->top==S->base)
returnERROR;
S->top--;
*e=*(S->top);
returnOK;
}
//從棧底到棧頂依次對S的每個元素調用函數Visit(),一旦失敗操作無效
StatusListTraverse(SqStackS,Status(*visit)(SElemType)){
SElemType*p;
p=S.base;
for(p=S.base;p<S.top;p++)
(*visit)(*p);

returnOK;
}
//輸出元素e
Statusoutput(SElemTypee){
printf("%d",e);

returnOK;
}

⑦ 怎麼用C語言棧實現表達式求值

這個問題不是一兩句話可以解釋清楚的。這個要涉及到計算機編譯原理課程的基本知識。其主要技術涉及到:表達式的分析與求值。表達式的分析與求值分為:前綴、中綴、及後綴。再具體的編程必須要參考 C 語言編程的書籍。我那會兒編程使用的書籍是《C 語言大全》,該書雖然比較老了,但是上面有很多現成的源代碼可供參考。

⑧ 編寫程序對表達式求值C語言

#include "stdio.h"
#include "malloc.h"

#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2

typedef int Status;
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10

typedef struct{
SElemType *base;
SElemType *top;
int stacksize;
}SqStack;
//構造一個空棧
Status InitStack(SqStack *S){
S->base = (SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType));

if(!S->base)
exit(OVERFLOW);
S->top=S->base;
S->stacksize=STACK_INIT_SIZE;
return OK;
}
//判斷是否為空棧
Status StackEmpty(SqStack S){
if(S.top == S.base)
return TRUE;
else
return FALSE;
}
//用e返回S的頂元素
Status GetTop(SqStack S, SElemType *e){
if(S.top == S.base)
return ERROR;
*e = *(S.top-1);
return OK;
}
//插入e為新的頂元素
Status Push(SqStack *S, SElemType e){
if((S->top - S->base) >= S->stacksize){
S->base = (
SElemType*)realloc(S->base,
(S->stacksize+STACKINCREMENT)*sizeof(SElemType)
);
if(!S->base)
exit(OVERFLOW);
S->top = S->base +S->stacksize;
S->stacksize += STACKINCREMENT;
}
*(S->top)=e;
S->top++;
return OK;
}
//刪除S的頂元素,並用e返回其值
Status Pop(SqStack *S, SElemType *e){
if(S->top == S->base)
return ERROR;
S->top--;
*e = *(S->top);
return OK;
}
//從棧底到棧頂依次對S的每個元素調用函數Visit(),一旦失敗操作無效
Status ListTraverse(SqStack S,Status (*visit)(SElemType)){
SElemType *p;
p=S.base;
for(p=S.base;p<S.top;p++)
(*visit)(*p);

return OK;
}
//輸出元素e
Status output(SElemType e){
printf("%d ",e);

return OK;
}

實現表達式求值的代碼:
/*計算整數表達式的值
*表達式必須以#結束
*表達式中可以出現多位數字,
*表達式中可以出現空格
*運算符包括+,-,*,/,(,)
*運算結果可以是多位整數,並以整數的形式返回
*/
typedef int SElemType; /*放入堆棧的元素的類型*/
#include <ctype.h>
#include "stack_s.c"
/*判斷輸入的某個字元是否是運算符
*c表示輸入的字元
*op數組中存放系統能識別的運算符
*/
Status in(char c,char op[]){
char *p;
p=op;
while(*p != '\0'){
if(c == *p)
return TRUE;
p++;
}
return FALSE;
}
/*比較兩個運算符的優先順序
*a,b中存放待比較的運算符
*'>'表示a>b
*'0'表示不可能出現的比較
*/
char Precede(char a, char b){
int i,j;
char pre[][7]={
/*運算符之間的優先順序製作成一張表格*/
{'>','>','<','<','<','>','>'},
{'>','>','<','<','<','>','>'},
{'>','>','>','>','<','>','>'},
{'>','>','>','>','<','>','>'},
{'<','<','<','<','<','=','0'},
{'>','>','>','>','0','>','>'},
{'<','<','<','<','<','0','='}};
switch(a){
case '+': i=0; break;
case '-': i=1; break;
case '*': i=2; break;
case '/': i=3; break;
case '(': i=4; break;
case ')': i=5; break;
case '#': i=6; break;
}
switch(b){
case '+': j=0; break;
case '-': j=1; break;
case '*': j=2; break;
case '/': j=3; break;
case '(': j=4; break;
case ')': j=5; break;
case '#': j=6; break;
}
return pre[i][j];
}
/*進行實際的運算
*a,b中分別以整數的形式存放兩個待運算的操作數
*theta中存放代表操作符的字元
*結果以整數的形式返回
*/
int Operate(int a, char theta, int b){
int i,j,result;
i=a;
j=b;

switch(theta) {
case '+': result = i + j; break;
case '-': result = i - j; break;
case '*': result = i * j; break;
case '/': result = i / j; break;
}
return result;
}
/*從輸入緩沖區中獲得下一個整數或運算符,並通過n帶回到主調函數
*返回值為1表示獲得的是運算符
*返回值為0表示獲得的是整形操作數
*/
int getNext(int *n){
char c;
*n=0;
while((c=getchar())==' '); /*跳過一個或多個空格*/
if(!isdigit(c)){ /*通過函數判斷如果字元不是數字,那麼只能是運算符*/
*n=c;
return 1;
}
do { /*能執行到該條語句,說明字元是數字,此處用循環獲得連續的數字*/
*n=*n*10+(c-'0'); /*把連續的數字字元轉換成相對應的整數*/
c=getchar();
} while(isdigit(c)); /*如果下一個字元是數字,進入下一輪循環*/
ungetc(c,stdin); /*新讀入的字元不是數字,可能是運算符,為了不影響下次讀入,把該字元放回到輸入緩沖區*/
return 0;
}

int EvaluateExpression(){

int n;
int flag;
int c;
char x,theta;
int a,b;

char OP[]="+-*/()#";
SqStack OPTR;
SqStack OPND;

InitStack(&OPTR);
Push(&OPTR,'#');
InitStack(&OPND);
flag=getNext(&c);

GetTop(OPTR, &x);
while(c!='#' || x != '#')
{
if(flag == 0)
{
Push(&OPND,c);
flag = getNext(&c);
} else
{
GetTop(OPTR, &x);
switch(Precede(x, c))
{
case '<'://棧頂元素優先順序低
Push(&OPTR,c);
flag = getNext(&c);
break;
case '='://脫括弧並接受下一字元
Pop(&OPTR,&x);
flag = getNext(&c);
break;
case '>':// 退棧並將運算結果入棧
Pop(&OPTR, &theta);
Pop(&OPND,&b);
Pop(&OPND,&a);
Push(&OPND, Operate(a, theta, b));
break;
}
}
GetTop(OPTR, &x);
}
GetTop(OPND, &c);
return c;
}

void main(){
int c;
printf("Please input one expression:");
c=EvaluateExpression();
printf("Result=%d\n",c);
getch();
}

⑨ C語言編程(數據結構):表達式求值

/*在TC2 和 VC6下都可以順利運行。
做了一個下午。一定要用我這個噢。
有簡單的輸入錯誤檢測。有完整的說明和
注釋*/

#include<stdio.h> /*庫文件包含*/
#include<string.h> /*用於字元串操作*/
#include<stdlib.h> /*用於exit函數*/

/**************************************************************************
int check(char *c)
輸入參數:
char *c: 輸入的字元串
返回參數:
0:字元串中有不符合規定的字元
1: 字元串字元符合規定,沒有不符合規定的字元.
功能:
檢查字元串中有否除了 0-9, +,-,*,/,(,),之外的其他字元,
如果有,則返回0, 表示出現錯誤。
若沒有,則返回1,表式字元串符合規定。
**************************************************************************/
int check(char *c)
{
int k=0;
while(*c!='\0')
{
if((*c>='0' && *c<='9') || *c=='+' ||
*c=='-' || *c=='*' || *c=='/' ||
*c=='.' || *c=='(' || *c==')' )
{

}
else
{
printf("input error, there have the char not the math expression char!\n");
return 0;
}

if(*c=='(')
k++;
else if(*c==')')
k--;

c++;
}
if(k!=0)
{
printf("input error, there is not have correct bracket '()'!\n");
return 0;
}
return 1;
}

/**************************************************************************
void move(char *f, double *s,int p)

輸入參數:
char *f : 運算符數組
double *s: 數值數組
int p: 當前運算符數組位置。
返回參數:

功能:
將當前已經完成運算的運算符消去,同時將數值數組的位置調整以進行下一次運算。
傳入值p若為3
則當前符號的數組位置為3.
f[3]=f[3+1].......f[len-2]=f[len-1] f[len-1]='\0';
s[i]=s[i+1].......s[len-1]=s[len] 因為數值比運算符多一個。
***************************************************************************/

void move(char *f, double *s,int p)
{
int i=0,len=strlen(f);
for(i=p; i<len; i++) /*將已經運算過的符號,空出來的位置用後面的符號來填充,*/
{ /*即把乘和除號的位置用後面的加和減號填充*/
f[i]=f[i+1];
s[i]=s[i+1];
}
s[i]=s[i+1];
f[len-1]='\0';
}
/**************************************************************************
double convnum(char *c)
輸入參數:
char *c :由數字和小數點組成的字元,用以轉換成double型的數值。
返回參數:
num:返回轉換好的值。
功能:
將輸入的字元串先將其小數點以前的部分復制到temp[]數組中,
若有小數點,則將小數點之後的數值,也就是小數部分先進行計算,值存入num中
計算完成後,再對整數部分進行計算,值加上小數部分的值,存入num中。
***************************************************************************/
double convnum(char *c)
{
double num=0.0;
double a=1.0;
int i=0,p=0,len=0;
char temp[100];
int tempi=0;
int start=0;
int f=1; /*正負符號指示器,若為1則為正數,為-1,此數為負數*/

len=strlen&;;

if(c[0]=='-')
{
start=1;
f=-1;
}
for(i=start; i<len; i++)
{
if(c[i]=='.')
{
p=i;
break;
}
temp[tempi++]=c[i]; /*將整數部分復制到temp[]中*/
}
temp[tempi]='\0';

if(p!=0)
{
for(i=p+1;i<len;i++) /*將小數部分計算出來*/
{
if(c[i]=='.') /*如果有多餘的小數點,則表示輸入錯誤*/
{
printf("there is more that one dot '.' in number!error!\n");
exit(0);
}
a=a*0.1;
num+=(a*(c[i]-48));
}
}

a=1.0;

len=strlen(temp); /*計算整數部分*/
for(i=len-1;i>=0; i--)
{
num=num+(a*(temp[i]-48));
a*=10;
}

num=num*f;
return num;
}

/**************************************************************************
double good(char *c)
輸入參數:
char *c :即將進行運算的字元串型數學表達式。如3.5+(2*3/5)
返回參數:
s[0]:計算結果將放入s[0]中
功能:
將輸入的字元串中的數字分別調用convnum(char *c)函數進行數值變換,再將其依
次存入doulbe s[i]中,將加減乘除運算符依次存入字元串符號數組 char f[i]中,
然後如果遇到括弧,則將括弧內的字元串存入另一字元數組中,然後用此
good(char *c) 遞歸函數進行遞歸運算。 然後根據先乘除,後加減的順序對已
存入數組的數值根 據存入字元串符號數組的運算符進行運算。結果存入s[0]中。
返回最終結果。
***************************************************************************/
double good(char *c) /*可遞歸函數*/
{ /*取得數值字元串,並調用convnum轉換成double*/
char g[100],number[30]; /*g,保存當前的表達式串,number保存一個數的所有字元*/
char f[80]; /*保存所有的符號的堆棧*/
int fi=0; /*保存符號的位置指針*/
double s[80]; /*保存當前所有的數的一個堆棧*/
int si=0; /*保存數字位置指針*/
int k=0; /* 若k=1則表示有一對括弧*/
int num=0,i=0; /*num保存新括弧內的字元數,i 保存number里的字元位置*/
int cc=0; /*乘除符號數量*/
int jj=0; /*加減符號數量*/

while(*c!='\0')/*當p==1 和k==0時,表示已經把括弧里的內容全部復制到g[100]中了*/
{
k=0;
num=0;

switch(*c)
{
case '+': /*當前字元為+-乘除時則表示*/
case '-':
case '*':
case'/':
f[fi++]=*c;
if(*c=='*' || *c=='/')
cc++;
else
jj++;
if(*(c-1)!=')')
{
number[i]='\0';
i=0;/*完成一個數字的復制,其位置指針i=0*/

s[si++]=convnum(number);
}
break;
case'(': /*有括弧,則將當前括弧作用范圍內的全部字元保存,作為*/
k++; /*一個新的字元表達式進行遞歸調用good函數計算。*/
while(k>0)
{
c++;
g[num]=*c;
num++;
if(*c==')')
{
k--;
}
else if(*c=='(')
{
k++;
}
}
g[num-1]='\0';
num=0;/*完成一個括弧內容的復制,其位置指針num=0*/
s[si++]=good(g);
break;
default:
number[i++]=*c;

if(*(c+1)=='\0')
{ number[i]='\0';
s[si++]=convnum(number);
}
break;
}

c++;
}

f[fi]='\0';

i=0;
while(cc>0)
{
switch(f[i])
{
case '*': cc--;
s[i+1]=s[i]*s[i+1];
move(f,s,i);
break;
case '/': cc--;
s[i+1]=s[i]/(float)s[i+1];
move(f,s,i);
break;
default:
i++;
break;
}
}

i=0;
while(jj>0)
{
switch(f[i])
{
case '+': s[i+1]=s[i]+s[i+1];
jj--;
move(f,s,i);
break;
case '-': s[i+1]=s[i]-s[i+1];
jj--;
move(f,s,i);
break;
default:
printf("operator error!");
break;
}
}

return s[0];
}

void main()
{
char str[100];
double sum=0;
int p=1;

while(1)
{
printf("enter expression: enter 'exit' end of program\n");
scanf("%s",str);
p=strcmp(str,"exit");
if(p==0)
break;
p=check(str);

if(p==0)
continue;
sum=good(str);
printf("%s=%f",str,sum);
printf("\n");
}
printf("good bye!\n");
}

例:
enter expression: enter 'exit' end of program
3.5+(12.3*15+8-(3/2+1))*2+(3.2*3-5)/6(輸入)
3.5+(12.3*15+8-(3/2+1))*2+(3.2*3-5)/6=384.266667
enter expression: enter 'exit' end of program
china(輸入)
input error, there have the char not the math expression char!
enter expression: enter 'exit' end of program
exit(輸入)
good bye!

⑩ 《數據結構 課程設計》表達式求值 實驗報告


算術表達式求值演示
一、概述
數據結構課程設計,要求學生在數據結構的邏輯特性和物理表示、數據結構的選擇和應用、演算法的設計及其實現等方面,加深對課程基本內容的理解。同時,在程序設計方法以及上機操作等基本技能和科學作風方面受到比較系統和嚴格的訓練。
在這次的課程設計中我選擇的題目是算術表達式求值演示。表達式計算是實現程序設計語言的基本問題之一,也是棧的應用的一個典型例子。設計一個程序,演示用算符優先法對算術表達式求值的過程。深入了解棧和隊列的特性,以便在解決實際問題中靈活運用它們,同時加深對這種結構的理解和認識。
二、 系統分析

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)。空間上,由於是用數組來存儲輸入的表達式,用棧來存儲運算中的數據和運算符,而棧的本質也用到的數組,數組在定義時必須確定其大小。在不知表達式長度的情況下確定數組的長度確非易事,此時極易造成空間的浪費,因此空間性能不是很好。