Question

急问谁有把中缀表达式转化为后缀表达式并求值的C程序

C程序,用栈
谢谢
希望4月32号能得到答案
运行的可以的
用/**/写备注哈

Answer 1

#include
"stdafx.h"
#include
"iostream.h"
#include
"math.h"
#include
"time.h"
#define
TRUE
1
#define
FALSE
0
#define
ERROR
-1
typedef
int
Status;
//用模板实现的链式结构堆栈类
template
<枯笑class
T>
class
stack{
private:
struct
link{
T
data;
//结点数据域
link
*next;
//下一结点指针
link(T
Data,link*
Next){//结构体构造函数
data=Data;
next=Next;
}
}*head;
//堆栈顶指针
public:
stack();
//构造函数(初始化栈)
~stack();
//析构函数(销毁栈)
void
push(T
Data);
//压栈操作
T
gettop()const;
//取栈顶元素
T
pop();
//出栈操作
T
getvalue(int
index);
//返回栈底开始第INDEX个栈中值
void
traverse(int
n);
//遍历栈
N个数换行
int
empty();
//谨伍判断栈是否为空，1是，0非
int
sizeofstack();
//返回栈的大小
void
clear();
//清空栈
};
//类模板成员函数的实现
template<class
T>
stack<T>::stack()//构造函数
{
head=0;
}
template<class
T>
stack<T>::~stack()//析构函数
{
link*
cursor=head;
while(head)
{
cursor=cursor->next;
delete
head;
head=cursor;
}
}
template<class
T>void
stack<T>::push(T
Data)//压没晌含栈操作
{
head=new
link(Data,head);
}
template<class
T>T
stack<T>::gettop()const//取栈顶元素
{
return
head->data;
}
template<class
T>T
stack<T>::pop()//出栈操作
{
if(head==0)return
0;
T
result=head->data;
link*
oldhead=head;
head=head->next;
delete
oldhead;
return
result;
}
template
<class
T>T
stack<T>::getvalue(int
index)//返回栈底开始第INDEX个栈中值
{
link
*cursor=head;
int
i=1;
int
stacklen=sizeofstack();
if(index<=0||index>stacklen)return
0;
while(i<=(stacklen-index))
{
cursor=cursor->next;
i++;
}
return
cursor->data;
}
template
<class
T>
void
stack<T>::traverse(int
n)//遍历栈
{
link
*
cursor=head;
int
iEnterSign=1;//换行标识
while(cursor)
{
cout<<cursor->data<<"
";
if(iEnterSign%n==0)cout<<endl;
cursor=cursor->next;
iEnterSign++;
}
if((iEnterSign-1)%n!=0)cout<<endl;
}
template
<class
T>int
stack<T>::empty()
//判断栈是否为空，1是，0非
{
return
head==0?1:0;
}
template
<class
T>int
stack<T>::sizeofstack()
//返回栈的大小
{
int
size=0;
link
*cursor=head;
while(cursor)
{
cursor=cursor->next;
size++;
}
return
size;
}
template<class
T>
void
stack<T>::
clear()
//清空栈
{
link
*cursor=head;
while(cursor&&cursor->next)
{
cursor=cursor->next;
delete
head;
head=cursor;
}
}
int
Operator(char
ch)
{
if(ch=='+'||ch=='-'||ch=='*'||ch=='/'||ch=='('||ch==')'||ch=='#')
return(TRUE);
else
return(FALSE);
}
char
Precede(char
ch1,char
ch2)
{
char
ch;
switch(ch1)
{
case
'+':
case
'-':
{
switch(ch2)
{
case
'+':
case
'-':
case
')':
case
'#':
ch='>';break;
case
'*':
case
'/':
case
'(':
ch='<';break;
}
break;
}
case
'*':
case
'/':
{
if(ch2=='(')
ch='<';
else
ch='>';
break;
}
case
'(':
{
if(ch2==')')
ch='=';
else
ch='<';
break;
}
case
')':
{
ch='>';
break;
}
case
'#':
{
if(ch2=='#')
ch='=';
else
ch='<';
break;
}
}
return(ch);
}
int
calc(int
x,char
ch,int
y)
{
int
z;
switch(ch)
{
case
'+':
z=x+y;
break;
case
'-':
z=x-y;
break;
case
'*':
z=x*y;
break;
case
'/':
z=x/y;
break;
}
return(z);
}
int
postexpression(char
*exp)
{
stack<int>
*opnd=new(stack<int>);
char
ch=*exp;
int
x=0,y,z,flag=FALSE;
int
result;
while(ch!='#')
{
if(!Operator(ch))
{
if(ch!='
')
{
x=x*10+(int)(ch)-48;
flag=TRUE;
}
else
{
if(flag)opnd->push(x);
x=0;
flag=FALSE;
}
}
else
{
x=opnd->pop();
y=opnd->pop();
z=calc(y,ch,x);
opnd->push(z);
}
ch=*(++exp);
}
result=opnd->pop();
return(result);
}
int
middexpression(char
*exp)
{
stack<int>
*opnd=new(stack<int>);
stack<char>
*optr=new(stack<char>);
char
ch=*exp;
int
x=0,y,z;
int
result;
optr->push('#');
while(ch!='#'||optr->gettop()!='#')
{
if(!Operator(ch))
{
x=x*10+(int)(ch)-48;
if(Operator(*(exp+1)))
{
opnd->push(x);
x=0;
}
ch=*++exp;
}
else
{
switch(Precede(optr->gettop(),ch))
{
case
'<'://栈顶元素优先权低
optr->push(ch);
ch=*++exp;
break;
case
'='://脱括号并接收下一字符
optr->pop();
ch=*++exp;
break;
case
'>'://退栈并将运算结果入栈
x=opnd->pop();
y=opnd->pop();
z=calc(y,optr->pop(),x);
opnd->push(z);
x=0;
break;
}
}
}
result=opnd->pop();
return(result);
}
void
main(void)//程序入口函数
{
clock_t
t1,t2,t3,t4;
int
i,n=9000;
t1=clock();
for(i=0;i<n;i++)
postexpression("100
200
50
3
*
-
13
8
-
/
+#");
//postexpression("100
200
50
8
45
9
/
-
-
+
#");
//postexpression("9
6
*
3
/
7
+
13
-#");
t2=clock();
printf("%10f\n",(t2-t1)/18.2/n);
t3=clock();
for(i=0;i<n;i++)
middexpression("100+(200-50*3)/(13-8)#");
//middexpression("100+(200-(50*(8-45/9)))#");
//middexpression("9*6/3+7-13#");
t4=clock();
printf("%10f\n",(t4-t3)/18.2/n);
printf("%10f",(t4-t3)/18.2/(t2-t1)*18.2);
cin.get();

Answer 2

#include "stdafx.h"
#include "iostream.h"
#include "math.h"
#include "time.h"
#define TRUE 1
#define FALSE 0
#define ERROR -1
typedef int Status;
//兄饥带用模板实现的链式结构堆栈类
template <class T>
class stack{
private:
struct link{
T data; //结点数据域
link *next; //下一结点指针
link(T Data,link* Next){//结构体构造函数
data=Data;
next=Next;
}
}*head; //堆栈顶指针肢颂
public:
stack(); //构造函数(初始化栈)
~stack(); //析构羡芦函数(销毁栈)
void push(T Data); //压栈操作
T gettop()const; //取栈顶元素
T pop(); //出栈操作
T getvalue(int index); //返回栈底开始第INDEX个栈中值
void traverse(int n); //遍历栈 N个数换行
int empty(); //判断栈是否为空，1是，0非
int sizeofstack(); //返回栈的大小
void clear(); //清空栈
};
//类模板成员函数的实现
template<class T> stack<T>::stack()//构造函数
{
head=0;
}
template<class T> stack<T>::~stack()//析构函数
{
link* cursor=head;
while(head)
{
cursor=cursor->next;
delete head;
head=cursor;
}
}
template<class T>void stack<T>::push(T Data)//压栈操作
{
head=new link(Data,head);
}
template<class T>T stack<T>::gettop()const//取栈顶元素
{
return head->data;
}
template<class T>T stack<T>::pop()//出栈操作
{
if(head==0)return 0;
T result=head->data;
link* oldhead=head;
head=head->next;
delete oldhead;
return result;
}
template <class T>T stack<T>::getvalue(int index)//返回栈底开始第INDEX个栈中值
{
link *cursor=head;
int i=1;
int stacklen=sizeofstack();
if(index<=0||index>stacklen)return 0;
while(i<=(stacklen-index))
{
cursor=cursor->next;
i++;
}
return cursor->data;
}
template <class T> void stack<T>::traverse(int n)//遍历栈
{
link * cursor=head;
int iEnterSign=1;//换行标识
while(cursor)
{
cout<<cursor->data<<" ";
if(iEnterSign%n==0)cout<<endl;
cursor=cursor->next;
iEnterSign++;
}
if((iEnterSign-1)%n!=0)cout<<endl;
}
template <class T>int stack<T>::empty() //判断栈是否为空，1是，0非
{
return head==0?1:0;
}
template <class T>int stack<T>::sizeofstack() //返回栈的大小
{
int size=0;
link *cursor=head;
while(cursor)
{
cursor=cursor->next;
size++;
}
return size;
}
template<class T> void stack<T>:: clear() //清空栈
{
link *cursor=head;
while(cursor&&cursor->next)
{
cursor=cursor->next;
delete head;
head=cursor;
}
}
int Operator(char ch)
{
if(ch=='+'||ch=='-'||ch=='*'||ch=='/'||ch=='('||ch==')'||ch=='#')
return(TRUE);
else
return(FALSE);
}
char Precede(char ch1,char ch2)
{
char ch;
switch(ch1)
{
case '+':
case '-':
{
switch(ch2)
{
case '+':
case '-':
case ')':
case '#':
ch='>';break;
case '*':
case '/':
case '(':
ch='<';break;
}
break;
}
case '*':
case '/':
{
if(ch2=='(')
ch='<';
else
ch='>';
break;
}
case '(':
{
if(ch2==')')
ch='=';
else
ch='<';
break;
}
case ')':
{
ch='>';
break;
}
case '#':
{
if(ch2=='#')
ch='=';
else
ch='<';
break;
}
}
return(ch);
}
int calc(int x,char ch,int y)
{
int z;
switch(ch)
{
case '+': z=x+y; break;
case '-': z=x-y; break;
case '*': z=x*y; break;
case '/': z=x/y; break;
}
return(z);
}
int postexpression(char *exp)
{
stack<int> *opnd=new(stack<int>);
char ch=*exp;
int x=0,y,z,flag=FALSE;
int result;
while(ch!='#')
{
if(!Operator(ch))
{
if(ch!=' ')
{
x=x*10+(int)(ch)-48;
flag=TRUE;
}
else
{
if(flag)opnd->push(x);
x=0;
flag=FALSE;
}
}
else
{
x=opnd->pop();
y=opnd->pop();
z=calc(y,ch,x);
opnd->push(z);
}
ch=*(++exp);
}
result=opnd->pop();
return(result);
}
int middexpression(char *exp)
{
stack<int> *opnd=new(stack<int>);
stack<char> *optr=new(stack<char>);
char ch=*exp;
int x=0,y,z;
int result;
optr->push('#');
while(ch!='#'||optr->gettop()!='#')
{
if(!Operator(ch))
{

x=x*10+(int)(ch)-48;
if(Operator(*(exp+1)))
{
opnd->push(x);
x=0;
}
ch=*++exp;
}
else
{
switch(Precede(optr->gettop(),ch))
{
case '<'://栈顶元素优先权低
optr->push(ch);
ch=*++exp;
break;
case '='://脱括号并接收下一字符
optr->pop();
ch=*++exp;
break;
case '>'://退栈并将运算结果入栈
x=opnd->pop();
y=opnd->pop();
z=calc(y,optr->pop(),x);
opnd->push(z);
x=0;
break;
}
}
}
result=opnd->pop();
return(result);
}
void main(void)//程序入口函数
{
clock_t t1,t2,t3,t4;
int i,n=9000;
t1=clock();
for(i=0;i<n;i++)
postexpression("100 200 50 3 * - 13 8 - / +#");
//postexpression("100 200 50 8 45 9 / - - + #");
//postexpression("9 6 * 3 / 7 + 13 -#");
t2=clock();
printf("%10f\n",(t2-t1)/18.2/n);

t3=clock();
for(i=0;i<n;i++)
middexpression("100+(200-50*3)/(13-8)#");
//middexpression("100+(200-(50*(8-45/9)))#");
//middexpression("9*6/3+7-13#");
t4=clock();
printf("%10f\n",(t4-t3)/18.2/n);

printf("%10f",(t4-t3)/18.2/(t2-t1)*18.2);
cin.get();