数据结构：字符数组。
概要设计：自定义一个栈类，包含char和int两种类型的数组。定义一个容量为100的字符数组，将数字放入数字栈中，将运算符放入字符栈中。出栈规则：当前入栈的运算符比栈顶的运算符优先级低。
详细设计： 1.栈中私有部分定义了整型变量top和char、int两种类型的数组，可利用同名但变量不同的函数push分别将数字和运算符放入不同栈内。 2. 主函数中定义一个容量为100的字符数组，利用ACSII码识别出数字和运算符，利用map函数将数字字符转化为int型。 3创建两个类对象，分别表示数字栈和运算符栈，将数字放入数字栈中，将运算符放入字符栈中。 4.写一个可以区分运算符优先级的函数。 5.写一个用来识别运算符并计算的函数。 6.最后运算结束时用top函数获得数字栈顶端的值，也就是运算结果。
#include<iostream> #include<string> #include<map> using namespace std; map<char,int> mp; class stack { private: int top,num[100]; char op[100]; public: stack() { top=0; } bool empty() { if(top == 0) return true; return false; } bool full() { if(top==99) return true; return false; } void push(int x) { num[top]=x; top++; } void push(char y) { op[top]=y; top++; } int top_() { return num[top-1]; } char _top_() { return op[top-1]; } void pop() { top--; } }; stack num; stack op; 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; } void count() { int m=num.top_(); num.pop(); int n=num.top_(); num.pop(); if(op._top_()=='+') num.push(m+n); if(op._top_()=='-') num.push(n-m); if(op._top_()=='*') num.push(m*n); if(op._top_()=='/') 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(op.full()||num.full()) break; 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._top_())||str[i]=='('||str[i]==')')//待入栈运算符优先级高或是'('和')'push { op.push(str[i]); if(str[i]==')') //为')'时先pop')' { op.pop(); if(op._top_()!='(') //op.top不为'('时计算括号中运算符 { count(); } op.pop(); //pop掉'(' } } else //待入栈运算符str[i]优先级低于op.top时先对栈顶运算符进行计算 { count(); op.push(str[i]); //将str[i]放入op栈中 } if(op._top_()=='=') break; } } if(op._top_()=='=') { op.pop(); while(op.empty()!=1) { count(); } } return num.top_(); } int main() { string str; cin>>str; int jg=account(str); cout<<jg<<endl; return 0; }运行结果
