中綴表達式求值演算法

1. 中綴表達式求解

中綴表達式轉化成後綴表達式並求值的演算法

#include<stdio.h>
#include<stdlib.h>
#define TRUE 1
#define FALSE 0
#define MAXNUM 100
typedef int DataType;
struct SeqStack
{ DataType s[MAXNUM];
int t;
};
typedef struct SeqStack *PSeqStack;
PSeqStack createEmptyStack_seq()
{
PSeqStack pastack;
pastack = (PSeqStack)malloc(sizeof(struct SeqStack));
if (pastack == NULL)
printf("Out of space!!\n");
else
pastack->t = -1;
return pastack;
} int isEmptyStack_seq(PSeqStack pastack)
{
return pastack->t == -1;
} void push_seq(PSeqStack pastack, DataType x)
{
if (pastack->t >= MAXNUM - 1)
printf("Overflow!\n");
else
{
pastack->t = pastack->t + 1;
pastack->s[pastack->t] = x;
}
} void pop_seq(PSeqStack pastack)
{
if (pastack->t == -1)
printf("Underflow!\n");
else
pastack->t = pastack->t - 1;
} DataType top_seq(PSeqStack pastack)
{
return pastack->s[pastack->t];
} int infixtoSuffix(const char * infix, char * suffix)
{ /*將中綴表達式轉換為後綴表達式，順利轉換返回true，若轉換過程中發現中綴表達式非法則返回false*/
int state_int = FALSE;
/*state_int記錄狀態，等於true表示剛讀入的是數字字元，等於false表示剛讀入的不是數字字元，
設置這個變數是為了在每輸出一個整數後輸出一個空格，以免連續輸出的兩個整數混在一起。*/
char c, c2;
PSeqStack ps = createEmptyStack_seq(); /*運算符棧*/
int i, j = 0;
if (infix[0] == '\0')
return FALSE; /*不允許出現空表達式*/
for (i = 0; infix[i] != '\0'; i++)
{
c = infix[i];
switch (c)
{
case ' ':
case '\t':
case '\n':
if (state_int == TRUE)
suffix[j++] = ' ';/*狀態從true轉換為false時輸出一個空格*/
state_int = FALSE;
break; /*遇到空格或製表符忽略*/
case '0':
case '1':
case '2':
case '3':
case '4':
case '5':
case '6':
case '7':
case '8':
case '9':
state_int = TRUE;
suffix[j++] = c; /*遇到數字輸出*/
break;
case '(':
if (state_int == TRUE)
suffix[j++] = ' ';/*狀態從true轉換為false時輸出一個空格*/
state_int = FALSE;
push_seq(ps, c); /*遇到左括弧，入棧*/
break;
case ')':
if (state_int == TRUE)
suffix[j++] = ' ';/*狀態從true轉換為false時輸出一個空格*/
state_int = FALSE;
c2 = ')';
while (!isEmptyStack_seq(ps))
{
c2 = top_seq(ps);/*取棧頂*/
pop_seq(ps); /*出棧*/
if (c2 == '(')
{
break;
}
suffix[j++] = c2;
}
if (c2 != '(')
{
free(ps);
suffix[j++] = '\0';
return FALSE;
}
break;
case '+':
case '-':
if (state_int == TRUE)
suffix[j++] = ' ';
state_int = FALSE;
while(!isEmptyStack_seq(ps))
{
c2 = top_seq(ps);
if (c2 == '+' || c2 == '-' || c2 == '*' || c2 == '/')
{
pop_seq(ps);
suffix[j++] = c2;
}
else if(c2=='(') break;
}
push_seq(ps, c);
break;
case '*':
case '/':
if (state_int == TRUE)
suffix[j++] = ' ';
state_int = FALSE;
while (!isEmptyStack_seq(ps))
{
c2 = top_seq(ps);
if (c2 == '*' || c2 == '/')
{
pop_seq(ps);
suffix[j++] = c2;
}
else if(c2=='+'||c2=='-'||c2=='(') break;
}
push_seq(ps, c);
break;
default:
free(ps);
suffix[j++] = '\0';
return FALSE;
}
}
if (state_int == TRUE) suffix[j++] = ' ';
while (!isEmptyStack_seq(ps))
{
c2 = top_seq(ps);
pop_seq(ps);
if (c2 == '(')
{
free(ps);
suffix[j++] = '\0';
return FALSE;
}
suffix[j++] = c2;
}
free(ps);
suffix[j++] = '\0';
return TRUE;
} int calculateSuffix(const char * suffix, int * presult)
{

int state_int = FALSE;
PSeqStack ps = createEmptyStack_seq();
int num = 0, num1, num2;
int i;
char c;
for (i = 0; suffix[i] != '\0'; i++)
{
c = suffix[i];
switch (c)
{
case '0':
case '1':
case '2':
case '3':
case '4':
case '5':
case '6':
case '7':
case '8':
case '9':
if (state_int == TRUE)
num = num * 10 + c - '0';
else num = c - '0';
state_int = TRUE;
break;
case ' ':
case'\t':
case '\n':
if (state_int == TRUE)
{
push_seq(ps, num);
state_int = FALSE;
}
break;
case '+':
case '-':
case '*':
case '/':
if (state_int == TRUE)
{
push_seq(ps, num);
state_int = FALSE;
}
if (isEmptyStack_seq(ps))
{
free(ps);
return FALSE;
}
num2 = top_seq(ps);
pop_seq(ps);
if (isEmptyStack_seq(ps))
{
free(ps);
return FALSE;
}
num1 = top_seq(ps);
pop_seq(ps);
if (c == '+')
push_seq(ps, num1 + num2);
if (c == '-')
push_seq(ps, num1 - num2);
if (c == '*')
push_seq(ps, num1 * num2);
if (c == '/')
push_seq(ps, num1 / num2);
break;
default:
free(ps);
return FALSE;
}
}
*presult = top_seq(ps);
pop_seq(ps);
if (!isEmptyStack_seq(ps))
{
free(ps);
return FALSE;
}
free(ps);
return TRUE;
} void getline(char * line, int limit)
{
char c;
int i = 0;
while (i < limit - 1 && (c = getchar()) != EOF && c != '\n')
line[i++] = c;
line[i] = '\0';
} void main()
{ char c, infix[MAXNUM], suffix[MAXNUM];
int result;
int flag = TRUE;
while (flag == TRUE)
{
printf("Plese input an infix expression!\nInput:");
getline(infix, MAXNUM);
if(infixtoSuffix(infix, suffix) == TRUE)
printf("suffix:%s\n", suffix);
else
{
printf("Invalid infix!\n");
printf("\nContinue? (y/n)");
scanf("%c", &c);
if (c == 'n' || c == 'N') flag = FALSE;
while (getchar() != '\n');
printf("\n");
continue;
}
if(calculateSuffix(suffix, &result) == TRUE)
printf("Result:%d\n", result);
else
printf("Invalid suffix!\n");
printf("\nContinue? (y/n)");
scanf("%c", &c);
if (c == 'n' || c == 'N') flag = FALSE;
while (getchar() != '\n');
printf("\n");
}
}

2. c語言計算中綴表達式

#include<iostream.h>
#include<math.h>
char input[1000];
double temp;
int i;
int left,right;
double getnumber(int begin,int end)
{
if(input[begin]=='+'||input[begin]=='-'||input[begin]=='*'||input[begin]=='/'||input[begin]=='^')
{
throw 2;
}
if(input[begin]=='0')
{
throw 3;
}
if(input[begin]=='(')
{
if(input[end-1]!=')') throw 1;
return getnumber(begin+1,end-1);
}
else
{
if(input[end-1]==')') throw 1;
}

for(i=begin;i<=end;i++)
{
if(input[i]=='+') return getnumber(begin,i-1)+getnumber(i+1,end);
if(input[i]=='-') return getnumber(begin,i-1)-getnumber(i+1,end);
if(input[i]=='*') return getnumber(begin,i-1)*getnumber(i+1,end);
if(input[i]=='/') return getnumber(begin,i-1)/getnumber(i+1,end);
if(input[i]=='^') return pow(getnumber(begin,i-1),getnumber(i+1,end));
}
temp=0;
for(i=begin;i<=end;i++)
{
temp*=10;
temp+=input[i]-'0';
}
return temp;

}
void main()
{
cin>>input;
int j=0;
while(input[j]!=NULL) j++;
try
{
cout<<getnumber(0,j-1);
}
catch(int x)
{
switch(x)
{
case 1:cout<<"部分括弧缺失";break;
case 2:cout<<"部分操作數缺失";break;
case 3:cout<<"部分操作數以0開頭";break;
default:cout<<"運算式無錯";
}
}
}
用C++寫的

3. 中綴表達式轉換為前綴及後綴表達式並求值 c++

#include using namespace std; bool IsOperator(char ch) { char ops[] = "+-*/"; for (int i = 0; i < sizeof(ops) / sizeof(char); i++) { if (ch == ops[i]) return true; } return false; } /////////////////////////////////////////////...
中綴表達式轉換成後綴表達式並求值 演算法： 中綴表達式轉後綴表達式的方法： 1.遇到操作數：直接輸出（添加到後綴表達式中） 2.棧為空時，遇到運算符，直接入棧 3.遇到左括弧：將其入棧 4.遇到右括弧：執行出棧操作，並將出棧的元素輸出，直到彈...

4. 數據結構：C語言描述棧的應用——算符優先法求中綴表達式的值

#include"iostream.h"
#include"math.h"
#include"stdlib.h"
class Calculator
{
public:
//介面方法聲明
void Run();

private:
//輔助函數
bool IsOperator(char ch);//判斷字元ch是否為操作符
char Precede(char theta1,char theta2);//判斷相繼出現的theta1和theta2的優先順序
double Operate(double left,char theta,double right,int[] &a);//執行運算letf theta right
void Get2Operands(LinkStack<double>&opnd,double &left,double &right);
//從棧opnd中退出兩個操作數
};

void Calculator::Get2Operands(LinkStack <double>&opnd,double &left,double &right)
{
}
bool Calculator:: IsOperator(char ch)
{
char ch;
cin>>ch;
if(ch=='+'||ch=='-'||ch=='*'||ch=='/'ch=='('ch==')'||ch=='=')
return true;
else
return false;
}

char Calculator:: Operate(double left,char theta,double right)
{ double result;
switch(theta)
{
case'+':result=left+right;break;
case'-':result=left-right;break;
case'*':result=left*right;break;
case'/':result=left/right;break;
}
return result;
}

char Calculator:: Precede(char theta1,char theta2)
{
char ch;
switch(theta1)
{
case'+':
case'-':
{
switch (theta2)
{
case'+':
case'-':
case')':
case'=':
ch='>';
break;
case'*':
case'/':
case'(':
ch='<';
break;
}
break;
}
case'*':
case'/':
{
if(theta2=='(')
ch='<';
else
ch='>';
break;
}
case'(':
{
if(theta2==')')
ch='=';
else ch='<';
break;
}
case')':
{
ch='>';
break;
}
case'=':
{
if(theta2=='=')
ch='=';
else
ch='<';
break;
}
}
return ch;
}

//方法Run()演算法實現如下
void Calculator::Run()
{//操作結果:按算符優先法進行表達式求值計算
LinkStack<double> opnd; //操作數棧
LinkStack<char>optr; //操作符棧
optr.push('='); //在optr棧中加入一個'='
char ch; //臨時字元
char optrTop; //臨時optr棧棧頂字元
double operand; //操作數
char theta; //操作符
cin>>ch; //從輸入流獲取一字元ch
while((optr.Top(optrTop),optrTop!='=')||ch!='=')
{
if(!IsOperator(ch))
{//ch不是操作字元
cin.putback(ch); //將字元放ch回輸入流
cin>>operand; //讀操作數operand
opnd.Push(operand); //進入opnd棧
cin>>ch; //讀入下一字元ch
}

else
{//ch是操作符
switch(Precede(optrTop,ch))
{
case'<':
optr.Push(ch);
cin>>ch;
break;
case'=':
optr.Pop(optr Top);
cin>>ch;
break;
case'>':
double left,right;
Get2Operands(opnd,left,right);
optr.Pop(theta);
opnd.Push(Operate(left,theta,right));
break;
case'e':
cout<<"操作符匹配出錯"<<endl;
exit(2);
}
}
}

opnd.Top(operand);
cout<<"表達式值為:"<<operand<<endl;
}

void main(void)
{

system("pause");
return 0;
}

5. 寫出對應的中綴算術表達式

(24+8)*3/4*(10-7)

6. 後綴表達式求值演算法

1 後綴表達式的求值
將中綴表達式轉換成等價的後綴表達式後，求值時，不需要再考慮運算符的優先順序，只需從左到右掃描一遍後綴表達式即可。具體求值步驟為：從左到右掃描後綴表 達式，遇到運算符就把表達式中該運算符前面兩個操作數取出並運算，然後把結果帶回後綴表達式；繼續掃描直到後綴表達式最後一個表達式。
例如，後綴表達式(abc*+def*/-) 的求值

2 後綴表達式的求值的演算法
設置一個棧，開始時，棧為空，然後從左到右掃描後綴表達式，若遇操作數，則進棧；若遇運算符，則從棧中退出兩個元素，先退出的放到運算符的右邊，後退出的 放到運算符左邊，運算後的結果再進棧，直到後綴表達式掃描完畢。此時，棧中僅有一個元素，即為運算的結果。
例，求後綴表達式：1 2 + 8 2 - 7 4 - / * 的值，
棧的變化情如下：

7. c++中綴表達式求值

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

#defineMAXSIZE100

//數字棧
typedefstructoprd{
	
	doubledata[MAXSIZE];
	inttop;

}OPRD;

//運算符棧
typedefstructoptr{

	chardata[MAXSIZE];
	inttop;

}OPTR;

//因為涉及到兩個棧的操作,所以將棧相關的操作用宏定義寫成函數,
//這樣就具有了通用性
//初始化棧
#defineInitStack(StackType,stack)	
{	
	*stack=(StackType*)malloc(sizeof(StackType));	
	*stack->top=-1;	
}

//判棧空
#defineEmptyStack(stack)	
(	
	stack->top==-1	
)

//判棧滿
#defineFullStack(stack)	
(	
	stack->top==MAXSIZE-1	
)

//入棧
#definePushStack(stack,value)	
{	
	if(!FullStack(stack)){	
		stack->top++;	
		stack->data[stack->top]=value;	
	}	
	else{	
		printf("棧已滿,無法入棧
");	
		exit(-1);	
	}	
}

//出棧
#definePopStack(stack,value)	
{	
	if(!EmptyStack(stack)){	
		*value=stack->data[stack->top];	
		stack->top--;	
	}	
	else{	
		printf("棧已空,無法出棧
");	
		exit(-1);	
	}	
}

//取棧頂元素
#defineGetStackTop(stack,value)	
{	
	if(!EmptyStack(stack)){	
		*value=stack->data[stack->top];	
	}	
	else{	
		printf("棧為空,無法取棧頂元素
");	
	}	
}

//優先順序表
charcompare(charch,chartop)
{
	switch(ch){
		case'+':
		case'-':
			if(top=='+'||top=='-'||top=='*'||top=='/')
				return'<';	//掃描的小於棧頂
			else
				return'>';	//掃描的大於棧頂
			break;
		case'*':
		case'/':
			if(top=='*'||top=='/')
				return'<';
			else
				return'>';
			break;
		case'(':
			if(top==')'){
				printf("輸入有誤!
");	exit(-1);
			}
			return'>';
			break;
		case')':
			if(top=='(')
				return'=';
			elseif(top=='#'){
				printf("輸入有誤!
");
				exit(-1);
			}
			else{
				return'<';
			}
			break;
		case'#':
			return'<';
	}
}

//輸入表達式並計算結果
doubleCalculateExp(void)
{
	doubleresult,tempNum1,tempNum2;
	doubledata=0,expn;
	charch,topSign,point='n',num='n';
	OPTR*sign;
	OPRD*number;

	InitStack(OPTR,&sign);
	InitStack(OPRD,&number);
	PushStack(sign,'#');
	printf("請輸入表達式：");
	ch=getchar();
	GetStackTop(sign,&topSign);

	while(ch!='#'||topSign!='#'){
		if('0'<=ch&&ch<='9'||ch=='.'){
			if(ch=='.'&&point=='y'){
				printf("表達式輸入有誤!
");
				exit(-1);
			}
			elseif(ch=='.'&&point=='n'){
				point='y';
				expn=0.1;
			}
			else{
				if(point=='y'){
					data=data+expn*(ch-'0');
					expn*=0.1;
				}
				else{
					data=data*10+(ch-'0');
				}
				num='y';
			}
			ch=getchar();
		}
		elseif(ch=='+'||ch=='-'||ch=='*'||ch=='/'||ch=='('||ch==')'||ch=='#'){
			if(num=='y'){
				PushStack(number,data);
				num='n';	point='n';
				data=0;
			}
			GetStackTop(sign,&topSign);
			switch(compare(ch,topSign)){
				case'<':		//掃描運算符優先順序小於棧頂元素
					PopStack(sign,&topSign);
					PopStack(number,&tempNum1);
					PopStack(number,&tempNum2);
					switch(topSign){
						case'+':	result=tempNum1+tempNum2;	break;
						case'-':	result=tempNum1-tempNum2;	break;
						case'*':	result=tempNum1*tempNum2;	break;
						case'/':	result=tempNum2/tempNum1;	break;
					}
					PushStack(number,result);
					break;
				case'>':		//掃描運算符優先順序大於棧頂元素
					PushStack(sign,ch);
					ch=getchar();
					break;
				case'=':		//掃描運算符為右括弧,匹配到了左括弧
					PopStack(sign,&topSign);
					ch=getchar();
					break;
			}
		}
		elseif(ch=='
'){
			ch='#';
		}
		else{
			printf("輸入的表達式有誤!
");
			exit(-1);
		}
		GetStackTop(sign,&topSign);
	}
	PopStack(number,&result);	//將結果從棧中取出來
	if(!EmptyStack(number)){//如果取出後棧不為空則表示輸入的表達式不正確
		printf("表達式有誤!
");
		exit(-1);
	}
	
	returnresult;
}

intmain(void)
{
	printf("%lf
",CalculateExp());
	
	return0;
}

8. 對一個合法的中綴表達式求值.簡單起見，假設表達式只含+

#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();
}

9. 計算中綴表達式

正好我們有一道上機題是要將中綴變後綴，再進行表達式求值，我把代碼全弄過來了，程序沒問題，你自己看吧
#include "stdio.h"
#include "stdlib.h"
#include "conio.h"

/*棧節點類型*/
typedef struct node
{
char data;
struct node *next;
}snode,*slink;
typedef struct node_post
{
int data;
struct node_post *next;
}pnode,*plink;

/*全局變數定義*/
slink top=NULL;
plink ptop=NULL;

/*棧空檢測，空時為1*/
int Emptystack()
{
if(top==NULL)return 1;
else return 0;
}

/*出棧，返回top中data*/
char Pop()
{
char e;
slink p;
if(top==NULL)return(-1);
else
{
p=top;
top=top->next;
e=p->data;
free(p);
return e;
}
}
int Pop_post()
{
int e;
plink p;
if(ptop==NULL)return(-1);
else
{
p=ptop;
ptop=ptop->next;
e=p->data;
free(p);
return e;
}
}

/*進棧*/
void Push(char e)
{
slink p;
p=(slink)malloc(sizeof(snode));
p->data=e;
p->next=top;
top=p;
}
void Push_post(int e)
{
plink p;
p=(plink)malloc(sizeof(pnode));
p->data=e;
p->next=ptop;
ptop=p;
}

/*取棧頂*/
char Gettop()
{ if(!Emptystack(top))return (top->data);
else return 0;
}

/*符號優先順序比較*/
int Precede(char x,char y)
{
int a,b;
switch(x)
{
case '#':a=-1;break; /*insert this line*/
case '(':a=0;break;
case '+':
case '-':a=1;break;
case '*':
case '/':a=2;break;
}
switch(y)
{
case '+':
case '-':b=1;break;
case '*':
case '/':b=2;break;
case '(':b=3;break;
}
if(a>=b)return 1;
else return 0;
}

/*中後續轉換*/
void mid_post(char mid[],char post[])
{
int i=0,j=0;
char c;
Push('#');
do
{ c=mid[i++];
switch(c)
{
case '#':
{
while(!Emptystack())
post[j++]=Pop();
}break;
case ')':
{ while(Gettop()!='(')
post[j++]=Pop();
Pop();
}break;
case '+':
case '-':
case '*':
case '/':
case '(':
{ while(Precede(Gettop(),c))
post[j++]=Pop();
Push(c);
}break;
default:post[j++]=c;
}
}while(c!='#');

}

/*後綴表達式求值*/
void Postcount(char post[])
{ int i=0;
char x,a,b;
int z;
while(post[i]!='#')
{ x=post[i];
switch(x)
{
case '+':b=Pop_post();a=Pop_post();z=a+b;Push_post(z);break;
case '-':b=Pop_post();a=Pop_post();z=a-b;Push_post(z);break;
case '*':b=Pop_post();a=Pop_post();z=a*b;Push_post(z);break;
case '/':b=Pop_post();a=Pop_post();z=a/b;Push_post(z);break;
default:z=atoi(&x);Push_post(z);
}
i++;
}
if(ptop!=NULL)printf("The result is: %d",ptop->data);
else printf("Failure");
}

void main()
{
char post[255]=" ",mid[255]=" ";
char jj;int j=0;
do
{
printf("please enter expression(\"#\" as end):\n");
scanf("%s",mid);
printf("the expression eaual:\n");
mid_post(mid,post);
printf("%s\n",post);
Postcount(post);
getchar();
printf("\ncontinue?(y/n)\n");
jj=getchar();
switch (jj)
{
case 'y':j=1;top=NULL;ptop=NULL;return(main());
case 'n':
default:j=0;
}
}while(j);
}

10. 中綴表達式求值。對0-9的數實用。輸入是按照字元型。這里乘法和除法的運算不對，字元和整型的轉換問題。

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
#include <conio.h>

int i,j,k/*計數器*/,top_opd/*操作數棧中的元素個數*/,top_op/*運算符棧中的元素個數*/,
flag/*用於字元串轉化為整數時的標記*/,num_1,num_2,result;
int num,operand_array[20]/*儲存輸入的操作數*/,operand_stack[20]/* 操作數棧*/;
char cr,num_str[20],operator_array[20]/*儲存輸入的運算符*/,operator_stack[20]/*運算符棧*/;

void Initial(void)/*初始化數組和計數器*/
{
for (k=0;k<=19;k++)
{
num_str[k]=NULL;
operator_array[k]=operator_stack[k]=NULL; /*與運算符有關的數組初始化 值為NULL*/
operand_array[k]=operand_stack[k]=-1; /*與操作數有關的數組初始化 值為-1*/
}
i=0; j=0; k=0; flag=0; top_op=-1; top_opd=-1;
}

void ScanString(void)/*掃描和提取輸入的字元串中的數字和運算符*/
{
do
{
cr=getch();
printf("%c",cr);

if ((cr>='0' && cr<='9')|| (cr=='.'))
{
num_str[i]=cr;
i++; flag=1;
}
else if (flag==1)
{
num=strtol(num_str,NULL,0); /*strtol函數將字元串轉化為整數*/
operand_array[j]=num; /*儲存輸入的操作數*/
for (k=0;k<=9;k++) num_str[k]=NULL;
i=0; j++; flag=0;
}
if (flag==0)
{ operator_array[j]=cr; j++; }/*儲存輸入的運算符*/
} while (cr!='=');
j--;
}

void Push_Operand(int opd)/*操作數的入棧*/
{
top_opd++;
operand_stack[top_opd]=opd;
}

void Push_Operator(char op)/*運算符的入棧*/
{
top_op++;
operator_stack[top_op]=op;
}

int Pop_Operand(void)/*操作數的出棧*/
{
int opd;
opd=operand_stack[top_opd];
operand_stack[top_opd]=-1;
top_opd--;
return(opd);
}

char Pop_Operator(void)/*運算符的出棧*/
{
char op;
op=operator_stack[top_op];
operator_stack[top_op]=NULL;
top_op--;
return(op);
}

int Calculate(int a,char op_temp,int b)/*四則運算的計算函數*/
{
int temp;
switch(op_temp)
{
case '+': temp=a+b; break;
case '-': temp=a-b; break;
case '*': temp=a*b; break;
case '/': temp=a/b; break;
default: printf("You Input a wrong character\n");
}
return(temp);
}

void Step(void)
/*操作數棧彈出兩個操作數並從運算符棧彈出的
一個運算符進行相應運算，結果存入操作數棧中*/
{
num_1=Pop_Operand();
num_2=Pop_Operand();
cr=Pop_Operator();
result=Calculate(num_2,cr,num_1);
Push_Operand(result);
}

int main(void)
/*演算法基本思想是逐字元從左到右順序讀入後綴表達式
若讀入的字元是操作數，則直接壓入棧，若是運算符
則與棧頂運算符比較，若級別高，則進棧，否則
從運算數棧彈出兩個操作數，和從運算符棧彈出的一個
運算符進行相應運算，結果存入操作數棧中。運算符再與
棧頂運算符比較優先順序。直至後綴表達式處理完畢。
這時操作棧中只剩一個數，即表達式結果。若遇到（
直接壓入運算符棧中,若遇到），則重復上面操作，
直至將（彈出棧 */
{
printf("請輸入一個四則運算表達式並以 = 結束");
Initial();
ScanString();
for (i=0;i<=j;i++)
{
if (operator_array[i]=='=')
{while (top_op>=0) Step(); break;}

if (operand_array[i]!=-1)
{Push_Operand(operand_array[i]);}

if (operator_array[i]!=NULL && (operator_array[i]!='=') &&(operator_array[i]!=')'))
{
while ((operator_array[i]=='+' || operator_array[i]=='-')&&
(operator_stack[top_op]=='*' || operator_stack[top_op]=='/' ||
operator_stack[top_op]=='+' || operator_stack[top_op]=='-'))
{Step();}
Push_Operator(operator_array[i]);
}

else if (operator_array[i]==')')
{
while (operator_stack[top_op]!='(')
{Step();}
cr=Pop_Operator();
cr=NULL;
}
}
printf("%d\n",result);
return(0);
}