首页 > 怎样将这个代码改为链栈结构?
头像
幻麟一面
编辑于 2021-04-06 10:25
+ 关注

怎样将这个代码改为链栈结构?

#include<iostream>
#include<string>
#include<cstdlib>
using namespace std;
template<class T>
class mystack
{
public:
mystack();
mystack(int initialCapacity){
stackLength=initialCapacity;
stack=new T[stackLength];     //stack为一个数组
stackTop=-1;//初始化栈顶元素
}
~mystack(){delete [] stack; }//析构
bool empty(){ return stackTop==-1;}//判空
int size(){ return stackTop+1;}//返回栈中元素个数
T & top()//返回栈顶元素
{
if(stackTop==-1){
cout<<"该栈为空"<<endl;
}
else return stack[stackTop];
}
void pop()//弹出栈顶元素
{
if(stackTop==-1){
cout<<"该栈为空"<<endl;
}
else stack[stackTop--];
}
void push(T theElement){//将theElement压入栈
if(stackTop==stackLength-1)//栈满扩充
{
stackLength*=2;      //栈的容量扩充二倍
T newStack[stackLength];
for(int i=0;i<stackLength;i++)
{
newStack[i]=stack[i];
}
delete stack;
stack=newStack;
}
stack[++stackTop]=theElement;
}
private:
int stackTop;
int stackLength;
T * stack;
};
void calculate(mystack<long int> &n, mystack<char> &c)
{ //定义运算
if(c.top()=='(') return;
long int a,b;
a=n.top();
//取数字栈栈顶元素
n.pop(); //弹出栈顶元素
b=n.top();
//取数字栈第二个元素
n.pop(); //弹出栈顶元素
switch(c.top())
{
case '+':
n.push(a+b);
break;
case '-':
n.push(b-a);
break;
case '*':
n.push(a*b);
break;
case '/':
n.push(b/a);
break;
default:break;
}
c.pop();//将运算完的符号弹出栈
}
void operate(string s,int length)
{
mystack<long int> n(length);     //声明一个数字栈
mystack<char> c(length);       //声明一个字符栈
for(int i=0;i<length;i++)
{
if(s[i]>='0'&&s[i]<='9')      //当输入为数字时
{
int k=s[i]-'0';
while(s[i+1]>='0'&&s[i+1]<='9')//如果下一个为数字 则记录整个数字
{
k=10*k+(s[i+1]-'0');
i++;
}
n.push(k);               //将读入的数字压到数字栈
}
else
{//读到字符
if((i==0||s[i-1]=='(')&&s[i]=='-')
{
continue;
}
switch(s[i]){
case '+':
case '-':
if(c.empty()||c.top()=='(') c.push(s[i]);//如果符号栈为空或者栈顶元素为(,+、-直接压入栈
else{
calculate(n,c);                      //+-运算符优先级最低,对之前运算先运算
if(!c.empty()&&c.top()!='(') calculate(n,c);
c.push(s[i]);                        //将读到的符号压入栈
}
break;
case '*':
case '/':
if(c.empty()||c.top()=='(') c.push(s[i]);
else if(c.top()=='+'||c.top()=='-') c.push(s[i]);
else if(c.top()=='*'||c.top()=='/')
{
calculate(n,c);
c.push(s[i]);
}
break;
case '(':
c.push(s[i]);
break;
case ')':
while (c.top()!='(') {
calculate(n,c);
}
c.pop();
break;
default:break;
}
}
}
cout<<"计算所得的结果是:";
while(!c.empty()) calculate(n,c);
cout<<n.top()<<endl;
}
int main()
{
string s;             //将输入的表达式存到一个字符串中
int length;           //记录字符串长度
cout<<"请输入一个运算表达式:"<<endl;
cin>>s;               //输入表达式
length=s.length();
operate(s,length);
return 0;
}

全部评论

(0) 回帖
加载中...
话题 回帖

推荐话题

相关热帖

近期热帖

近期精华帖

热门推荐