当前位置:编程学习 > C/C++ >>

用栈实现后缀式的加法(C++)

用栈实现后缀式的加法(C++)

比如33+44-(24+12)

帮我修改一下程序代码,谢谢啦

#include <iostream>
#include <cmath>
using namespace std;
const int Maxsize=100;
struct Stack
{double array[Maxsize];
 int top;
};
struct Stack1
{char array[Maxsize];
 int top;
};
extern void init(Stack &s);
extern bool IsEmpty(Stack &s);
extern void push(Stack &s,double x);
extern double Gettop(Stack &s);
extern double pop(Stack &s);
extern void Display(Stack &s);
extern void MakeEmpty(Stack &s);

extern void init1(Stack1 &s);
extern bool IsEmpty1(Stack1 &s);
extern void push1(Stack1 &s,char ch);
extern char Gettop1(Stack1 &s);
extern char pop1(Stack1 &s);
extern void Display1(Stack1 &s);
extern void MakeEmpty1(Stack1 &s);

extern bool get2values(Stack &s,double &left,double &right);
extern void DoOperator(Stack &s,char op);
extern bool IsOperand(char ch);
extern int Isp(char ch);
extern int Osp(char ch);
extern void postfix();

int main()
{Stack s;
init(s);
for(int i=0;i<10;i++)
{push(s,i);
}
Display(s);
pop(s);
Gettop(s);
Display(s);
postfix();
return 0;
}

void init(Stack &s)  //初始化栈
{s.top=-1;
}
bool IsEmpty(Stack &s)  //判断栈为空
{if(s.top<0) return true;
 else return false;
}
void push(Stack &s,double x)  //元素进栈
{if(s.top==Maxsize-1) cout<<"stack is full"<<endl;
else
{s.top++;
s.array[s.top]=x;
}
}
double Gettop(Stack &s)  //获得栈顶元素
{if(IsEmpty(s))
{cout<<"stack is empty"<<endl;
 return -1;
}
 else return s.array[s.top];
}
double pop(Stack &s)  //退栈
{if(IsEmpty(s))
{cout<<"stack is empty"<<endl;
 return -1;
}
else return s.array[s.top--];
}
void Display(Stack &s)  //打印栈里元素
{for(int i=s.top;i>=0;i--)
cout<<s.array[i]<<endl;
cout<<endl;
}
void MakeEmpty(Stack &s)  //清空栈
{while(!IsEmpty(s))
pop(s);
}

 

void init1(Stack1 &s)  //初始化栈
{s.top=-1;
}
bool IsEmpty1(Stack1 &s)  //判断栈为空
{if(s.top<0) return true;
 else return false;
}
void push1(Stack1 &s,char ch)  //元素进栈
{if(s.top==Maxsize-1) cout<<"stack is full"<<endl;
else
{s.top++;
s.array[s.top]=ch;
}
}
char Gettop1(Stack1 &s)  //获得栈顶元素
{if(IsEmpty1(s))
{cout<<"stack is empty"<<endl;
 return -1;
}
 else return s.array[s.top];
}
char pop1(Stack1 &s)  //退栈
{if(IsEmpty1(s))
{cout<<"stack is empty"<<endl;
 return -1;
}
else return s.array[s.top--];
}
void Display1(Stack1 &s)  //打印栈里元素
{for(int i=s.top;i>=0;i--)
cout<<s.array[i]<<endl;
cout<<endl;
}
void MakeEmpty1(Stack1 &s)  //清空栈
{while(!IsEmpty1(s))
pop1(s);
}

 


bool get2values(Stack &s,double &left,double &right)  //从栈中取出两个操作数
{if(IsEmpty(s))
{cout<<"Missing Operand!"<<endl;
 return false;
}
 right=pop(s);
 if(IsEmpty(s))
{cout<<"Missing Operand!"<<endl;
 return false;
}
 left=pop(s);
 return true;
}
void DoOperator(Stack &s,char op)  //取两个操作数,形成运算指令并计算
{double left,right;
bool result;
result=get2values(s,left,right);
if(result==true)
switch(op)
{case'+':push(s,left+right);break;
 case'-':push(s,left-right);break;
 case'*':push(s,left*right);break;
 case'/':if(right==0.0)
   {cout<<"Divide by 0!"<<endl;
       MakeEmpty(s);
   }
      else push(s,left/right);break;
 case'^':push(s,pow(left,right));break;
}
else MakeEmpty(s);
}
bool IsOperand(char ch)
{if(ch>='0'&&ch<='9')
return true;
else
return false;
}
int Isp(char ch)
{switch(ch)
{case'#':return 0;
 case'(':return 1;
 case'+':return 3;
 case'-':return 3;
 case'*':return 5;
 case'/':return 5;
 case'%':return 5;
 case'^':return 7;
 case')':return 8;
}
}
int Osp(char ch)
{switch(ch)
{case'#':return 0;
 case'(':return 8;
 case'+':return 2;
 case'-':return 2;
 case'*':return 4;
 case'/':return 4;
 case'%':return 4;
 case'^':return 6;
 case')':return 1;
}
}
void postfix()
{char c,e[256],topc;
int i=0;
Stack1 oper;
init1(oper);
MakeEmpty1(oper);
Stack num;
init(num);
MakeEmpty(num);
double n;
double buffer;
push1(oper,'#');
cout<<"请输入中缀式表达式:"<<endl;
cin>>e;
int j=0;
c=e[j];
while(c!='\0')
{
 if(IsOperand(c))
 {buffer=c-'0';
  while(IsOperand(e[j+1]))
  {buffer*=10;
   buffer+=(e[j+1]-'0');
   j++;                             
   c=e[j];
  }
  push(num,buffer);
  j++;
  c=e[j];
 }
 
 
 
 else
 {
  if(c==')')
 {topc=pop1(oper);
  while(topc!='(')
  {DoOperator(num,c);
   topc=pop1(oper);
  }
 }
  else
  {topc=Gettop1(oper);
   while(Isp(topc)>Osp(c))
   {topc=pop1(oper);
    DoOperator(num,c);
 topc=Gettop1(oper);
   }
   push1(oper,c);
  }
  j++;
  c=e[j];
 }

}

topc=pop1(oper);
while(topc!='#')
{DoOperator(num,c);     
 topc=pop1(oper);
}

n=pop(num);
cout<<n;
}

补充:不好意思,代码改动一点,如下

我能够实现33+44*5,却不能实现33+44*(2+3)

其它调用函数没错,就void postfix()有错

关键和括号有关的一小段代码有错

#include <iostream>
#include <cmath>
using namespace std;
const int Maxsize=100;
struct Stack
{double array[Maxsize];
 int top;
};
struct Stack1
{char array[Maxsize];
 int top;
};
extern void init(Stack &s);
extern bool IsEmpty(Stack &s);
extern void push(Stack &s,double x);
extern double Gettop(Stack &s);
extern double pop(Stack &s);
extern void Display(Stack &s);
extern void MakeEmpty(Stack &s);

extern void init1(Stack1 &s);
extern bool IsEmpty1(Stack1 &s);
extern void push1(Stack1 &s,char ch);
extern char Gettop1(Stack1 &s);
extern char pop1(Stack1 &s);
extern void Display1(Stack1 &s);
extern void MakeEmpty1(Stack1 &s);

extern bool get2values(Stack &s,double &left,double &right);
extern void DoOperator(Stack &s,char op);
extern bool IsOperand(char ch);
extern int Isp(char ch);
extern int Osp(char ch);
extern void postfix();

int main()
{Stack s;
init(s);
for(int i=0;i<10;i++)
{push(s,i);
}
Display(s);
pop(s);
Gettop(s);
Display(s);
postfix();
return 0;
}

void init(Stack &s)  //初始化栈
{s.top=-1;
}
bool IsEmpty(Stack &s)  //判断栈为空
{if(s.top<0) return true;
 else return false;
}
void push(Stack &s,double x)  //元素进栈
{if(s.top==Maxsize-1) cout<<"stack is full"<<endl;
else
{s.top++;
s.array[s.top]=x;
}
}
double Gettop(Stack &s)  //获得栈顶元素
{if(IsEmpty(s))
{cout<<"stack is empty"<<endl;
 return -1;
}
 else return s.array[s.top];
}
double pop(Stack &s)  //退栈
{if(IsEmpty(s))
{cout<<"stack is empty"<<endl;
 return -1;
}
else return s.array[s.top--];
}
void Display(Stack &s)  //打印栈里元素
{for(int i=s.top;i>=0;i--)
cout<<s.array[i]<<endl;
cout<<endl;
}
void MakeEmpty(Stack &s)  //清空栈
{while(!IsEmpty(s))
pop(s);
}

 

void init1(Stack1 &s)  //初始化栈
{s.top=-1;
}
bool IsEmpty1(Stack1 &s)  //判断栈为空
{if(s.top<0) return true;
 else return false;
}
void push1(Stack1 &s,char ch)  //元素进栈
{if(s.top==Maxsize-1) cout<<"stack is full"<<endl;
else
{s.top++;
s.array[s.top]=ch;
}
}
char Gettop1(Stack1 &s)  //获得栈顶元素
{if(IsEmpty1(s))
{cout<<"stack is empty"<<endl;
 return -1;
}
 else return s.array[s.top];
}
char pop1(Stack1 &s)  //退栈
{if(IsEmpty1(s))
{cout<<"stack is empty"<<endl;
 return -1;
}
else return s.array[s.top--];
}
void Display1(Stack1 &s)  //打印栈里元素
{for(int i=s.top;i>=0;i--)
cout<<s.array[i]<<endl;
cout<<endl;
}
void MakeEmpty1(Stack1 &s)  //清空栈
{while(!IsEmpty1(s))
pop1(s);
}

 


bool get2values(Stack &s,double &left,double &right)  //从栈中取出两个操作数
{if(IsEmpty(s))
{cout<<"Missing Operand!"<<endl;
 return false;
}
 right=pop(s);
 if(IsEmpty(s))
{cout<<"Missing Operand!"<<endl;
 return false;
}
 left=pop(s);
 return true;
}
void DoOperator(Stack &s,char op)  //取两个操作数,形成运算指令并计算
{double left,right;
bool result;
result=get2values(s,left,right);
if(result==true)
switch(op)
{case'+':push(s,left+right);break;
 case'-':push(s,left-right);break;
 case'*':push(s,left*right);break;
 case'/':if(right==0.0)
   {cout<<"Divide by 0!"<<endl;
       MakeEmpty(s);
   }
      else push(s,left/right);break;
 case'^':push(s,pow(left,right));break;
}
else MakeEmpty(s);
}
bool IsOperand(char ch)
{if(ch>='0'&&ch<='9')
return true;
else
return false;
}
int Isp(char ch)
{switch(ch)
{case'#':return 0;
 case'(':return 1;
 case'+':return 3;
 case'-':return 3;
 case'*':return 5;
 case'/':return 5;
 case'%':return 5;
 case'^':return 7;
 case')':return 8;
}
}
int Osp(char ch)
{switch(ch)
{case'#':return 0;
 case'(':return 8;
 case'+':return 2;
 case'-':return 2;
 case'*':return 4;
 case'/':return 4;
 case'%':return 4;
 case'^':return 6;
 case')':return 1;
}
}
void postfix()
{char c,e[256],topc;
int i=0;
Stack1 oper;
init1(oper);
MakeEmpty1(oper);
Stack num;
init(num);
MakeEmpty(num);
double n;
double buffer;
push1(oper,'#');
cout<<"请输入中缀式表达式:"<<endl;
cin>>e;
int j=0;
c=e[j];
while(c!='\0')
{
 if(IsOperand(c))
 {buffer=c-'0';
  while(IsOperand(e[j+1]))
  {buffer*=10;
   buffer+=(e[j+1]-'0');
   j++;                             
   c=e[j];
  }
  push(num,buffer);
  j++;
  c=e[j];
 }
 
 
 
 else
 {
  if(c==')')
 {topc=pop1(oper);
  while(topc!='(')
  {DoOperator(num,c);
   topc=pop1(oper);
  }
 }
  else
  {topc=Gettop1(oper);
   while(Isp(topc)>Osp(c))
   {topc=pop1(oper);
    DoOperator(num,c);
 topc=Gettop1(oper);
   }
   push1(oper,c);
  }
  j++;
  c=e[j];
 }

}

topc=pop1(oper);
while(topc!='#')
{DoOperator(num,topc);     
 topc=pop1(oper);
}

n=pop(num);
cout<<n;
}

答案:#include <iostream>
#include <cmath>
using namespace std;
const int Maxsize=100;
struct Stack
{double array[Maxsize];
 int top;
};
struct Stack1
{char array[Maxsize];
 int top;
};
extern void init(Stack &s);
extern bool IsEmpty(Stack &s);
extern void push(Stack &s,double x);
extern double Gettop(Stack &s);
extern double pop(Stack &s);
extern void Display(Stack &s);
extern void MakeEmpty(Stack &s);

extern void init1(Stack1 &s);
extern bool IsEmpty1(Stack1 &s);
extern void push1(Stack1 &s,char ch);
extern char Gettop1(Stack1 &s);
extern char pop1(Stack1 &s);
extern void Display1(Stack1 &s);
extern void MakeEmpty1(Stack1 &s);

extern bool get2values(Stack &s,double &left,double &right);
extern void DoOperator(Stack &s,char op);
extern bool IsOperand(char ch);
extern int Isp(char ch);
extern int Osp(char ch);
extern void postfix();

int main()
{Stack s;
init(s);
for(int i=0;i<10;i++)
{push(s,i);
}
Display(s);
pop(s);
Gettop(s);
Display(s);
postfix();
return 0;
}

void init(Stack &s)  //初始化栈
{s.top=-1;
}
bool IsEmpty(Stack &s)  //判断栈为空
{if(s.top<0) return true;
 else return false;
}
void push(Stack &s,double x)  //元素进栈
{if(s.top==Maxsize-1) cout<<"stack is full"<<endl;
else
{s.top++;
s.array[s.top]=x;
}
}
double Gettop(Stack &s)  //获得栈顶元素
{if(IsEmpty(s))
{cout<<"stack is empty"<<endl;
 return -1;
}
 else return s.array[s.top];
}
double pop(Stack &s)  //退栈
{if(IsEmpty(s))
{cout<<"stack is empty"<<endl;
 return -1;
}
else return s.array[s.top--];
}
void Display(Stack &s)  //打印栈里元素
{for(int i=s.top;i>=0;i--)
cout<<s.array[i]<<endl;
cout<<endl;
}
void MakeEmpty(Stack &s)  //清空栈
{while(!IsEmpty(s))
pop(s);
}

 

void init1(Stack1 &s)  //初始化栈
{s.top=-1;
}
bool IsEmpty1(Stack1 &s)  //判断栈为空
{if(s.top<0) return true;
 else return false;
}
void push1(Stack1 &s,char ch)  //元素进栈
{if(s.top==Maxsize-1) cout<<"stack is full"<<endl;
else
{s.top++;
s.array[s.top]=ch;
}
}
char Gettop1(Stack1 &s)  //获得栈顶元素
{if(IsEmpty1(s))
{cout<<"stack is empty"<<endl;
 return -1;
}
 else return s.array[s.top];
}
char pop1(Stack1 &s)  //退栈
{if(IsEmpty1(s))
{cout<<"stack is empty"<<endl;
 return -1;
}
else return s.array[s.top--];
}
void Display1(Stack1 &s)  //打印栈里元素
{for(int i=s.top;i>=0;i--)
cout<<s.array[i]<<endl;
cout<<endl;
}
void MakeEmpty1(Stack1 &s)  //清空栈
{while(!IsEmpty1(s))
pop1(s);
}

 


bool get2values(Stack &s,double &left,double &right)  //从栈中取出两个操作数
{if(IsEmpty(s))
{cout<<"Missing Operand!"<<endl;
 return false;
}
 right=pop(s);
 if(IsEmpty(s))
{cout<<"Missing Operand!"<<endl;
 return false;
}
 left=pop(s);
 return true;
}
void DoOperator(Stack &s,char op)  //取两个操作数,形成运算指令并计算
{double left,right;
bool result;
result=get2values(s,left,right);
if(result==true)
switch(op)
{case'+':push(s,left+right);break;
 case'-':push(s,left-right);break;
 case'*':push(s,left*right);break;
 case'/':if(right==0.0)
   {cout<<"Divide by 0!"<<endl;
       MakeEmpty(s);
   }
      else push(s,left/right);break;
 case'^':push(s,pow(left,right));break;
}
else MakeEmpty(s);
}
bool IsOperand(char ch)
{if(ch>='0'&&ch<='9')
return true;
else
return false;
}
int Isp(char ch)
{switch(ch)
{case'#':return 0;
 case'(':return 1;
 case'+':return 3;
 case'-':return 3;
 case'*':return 5;
 case'/':return 5;
 case'%':return 5;
 case'^':return 7;
 case')':return 8;
}
}
int Osp(char ch)
{switch(ch)
{case'#':return 0;
 case'(':return 8;
 case'+':return 2;
 case'-':return 2;
 case'*':return 4;
 case'/':return 4;
 case'%':return 4;
 case'^':return 6;
 case')':return 1;
}
}
void postfix()
{char c,e[256],topc;
int i=0;
Stack1 oper;
init1(oper);
MakeEmpty1(oper);
Stack num;
init(num);
MakeEmpty(num);
double n;
double buffer;
double temp;
int k;
push1(oper,'#');
cout<<"请输入中缀式表达式:"<<endl;
cin>>e;
int j=0;
c=e[j];
while(c!='\0')
{
 if(IsOperand(c))
 {buffer=c-'0';
  while(IsOperand(e[j+1]))
  {buffer*=10;
   buffer+=(e[j+1]-'0');
   j++;                             
   c=e[j];
  }
  while(e[j+1]=='.')
  {j+=2;
   c=e[j];
   k=1;
   temp=pow(0.1,k)*(c-'0');
   k++;
   while(IsOperand(e[j+1]))
   {temp+=pow(0.1,k)*(e[j+1]-'0');
    k++;
 j++;
 c=e[j];
   }
  }
  buffer+=temp;
  push(num,buffer);
  j++;
  c=e[j];
 }
 
 
 
 else
 {
  if(c==')')
 {topc=pop1(oper);
  while(topc!='(')
  {DoOperator(num,topc);
   topc=pop1(oper);
  }
 }
  else
  {topc=Gettop1(oper);
   while(Isp(topc)>Osp(c))
   {topc=pop1(oper);
    DoOperator(num,topc);
 topc=Gettop1(oper);
   }
   push1(oper,c);
  }
  j++;
  c=e[j];
 }

}

topc=pop1(oper);
while(topc!='#')
{DoOperator(num,topc);     
 topc=pop1(oper);
}

n=pop(num);
cout<<n;
}

上一个:有没有谁知道C++怎样学才最易学?
下一个:谁能帮忙做个C++程序啊 不胜感谢!

CopyRight © 2022 站长资源库 编程知识问答 zzzyk.com All Rights Reserved
部分文章来自网络,