中缀表达式求值算法

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