数据结构：链表 概要设计:将自写栈（数据结构为数组）版计算器的栈结构替换成链栈，栈外的其他部分可几乎不做改动，只将对应顺序栈中函数替换成对应链栈中函数。
自写栈版链接点这里 详细设计： 1.设置结点Node存储运算符，设置结点node存储数字。 2.在原本的代码中字符栈和数字栈写在了同一个栈类里，通过不同的数据类型调用同名函数。为了保证思路清晰，改编后的代码中写了两个链表栈类，数字栈numstack和字符栈opstack。 3.将栈类原本的判空函数删去，将链栈中各函数与原来的函数一一对应。
代码如下
#include<iostream> #include<string> #include<map> using namespace std; map<char,int> mp; struct Node{ char oper; Node *Next; }; struct node { int data; node *next; }; class numstack {private: node *top; public: numstack() { top=NULL; } ~numstack() { while(!empty()) pop();} bool empty() { return top==NULL;} int get_top() { return top->data;} void push(int x) { node *t = new node; t->data=x; t->next=NULL;//产生节点，装入元素到节点中（可以删掉但建议加上） t->next=top; top=t; //连接结点到表头 } void pop() { if(empty()) return ; node *o=top; top=top->next; delete o;} }; class opstack { private: Node *head; public: opstack() { head=NULL; } ~opstack() { while(!empty()) pop(); } bool empty() { return head==NULL; } char get_head() { return head->oper; } void push(char x) { Node *h = new Node; h->oper=x; h->Next=NULL; h->Next=head; head=h; } void pop() { if(empty()) return ; Node *e=head; head=head->Next; delete e; } }; int yxj(char a) { int k; if(a=='=') {k=0;} if(a=='('||a==')') {k=1;} if(a=='+'||a=='-') {k=2;} if(a=='*'||a=='/') {k=3;} return k; } numstack num; opstack op; void count() { int m=num.get_top(); num.pop(); int n=num.get_top(); num.pop(); if(op.get_head()=='+') num.push(m+n); if(op.get_head()=='-') num.push(n-m); if(op.get_head()=='*') num.push(m*n); if(op.get_head()=='/') num.push(n/m); op.pop(); //计算完毕后pop掉该运算符 } int account(string &str) { int len=str.size(); char c; int l,s,j; for (c = '0',l=0; c <= '9';c++,l++) //map方法将字符转化为整数 mp[c] = l; for(int i=0;i<len;++i) { if(str[i]>='0'&&str[i]<='9') { s=0; for(j=i;str[j]>='0'&&str[j]<='9';j++) { s=s*10+mp[str[j]]; } num.push(s); i=j-1; } else { if(op.empty()) //op栈为空时直接push { op.push(str[i]); } else if(yxj(str[i])>yxj(op.get_head())||str[i]=='('||str[i]==')')//待入栈运算符优先级高或是'('和')'push { op.push(str[i]); if(str[i]==')') //为')'时先pop')' { op.pop(); if(op.get_head()!='(') //op.top不为'('时计算括号中运算符 { count(); } op.pop(); //pop掉'(' } } else //待入栈运算符str[i]优先级低于op.top时先对栈顶运算符进行计算 { count(); op.push(str[i]); //将str[i]放入op栈中 } if(op.get_head()=='=') break; } } if(op.get_head()=='=') { op.pop(); while(op.empty()!=1) { count(); } } return num.get_top(); } int main() { string str; cin>>str; int jg=account(str); cout<<jg<<endl; return 0; }运行结果
