用栈实现后缀式的加法(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;
}