本博文源于严蔚敏老师的《数据结构》，今天就来聊聊如何实现一位数运算数加法和多位数运算符加法。本代码完全对书中的代码再现，没有其他的过多的想法，包括多位数运算法加法也只是对原有内容基础上修改罢了。如果读者对此非常感兴趣，也可以收藏进行深度学习一波。
1、原题再现实现表达式求值
2、测试效果 3、题目分析实现表达式求值是栈的应用，一般方法如下，用两个栈，一个运算符栈，一个是操作数栈，读入字符，遇见操作数比较栈顶运算符看是否入栈，还是弹出操作数进行操作，如果遇见操作数那就入栈，具体的流程如下：
为实现运算符优先算法，可以使用两个工作栈
OPTR栈:存储运算符栈
OPND:存储操作数或运算结果
In函数:判定读入的字符ch是否为运算符
Precede 是判定运算符栈的栈顶元素与读入的元素负之间优先关系的函数
Operate:为进行二元运算
步骤如下：
1、初始化OPTR栈和OPND栈，将表达式起始负“#”压入OPTR栈
2、扫描表达式，读入第一个字符ch，如果表达式没有扫描完毕至"#"或OPTR的栈顶元素不为 “#”则循环执行以下操作
2.1若ch不是运算符则压入OPND栈，读入下一个字符ch
2.2若ch是运算符，则根据OPTR的栈顶元素和ch的优先级比较结果，做不同的处理
2.3若是小于，则ch压入optr栈，读入下一个字符ch
2.4若是大于，则弹出optr栈顶的运算符，从OPND栈弹出两个数，进行相应运算，借故偶压入OPND栈，
2.5若是等于，则optr的栈顶元素是“（”且ch是”）“这时弹出OPTR栈顶的”（“相当于括号匹配成功，然后读入下一个字符1ch
3.opnd栈顶元素即为表达式求值结果，返回此元素
核心代码
核心代码就是对这核心步骤进行实现
int main(){
stack OPND;//运算数栈
stack OPTR;//运算操符栈
OPTR.push('#');//表达式起始”#“压入OPTR栈
char ch;
char theta;
int a,b,num=0;
cin >> ch;
while(ch != '#' || OPTR.top()!='#'){ //表达式没有扫描完毕或OPTR的栈顶元素不为“#”
if(!In(ch)){ //ch不是运算符则进OPND栈
num=num*10+(ch-'0');
cin >> ch;
if(In(ch)) {
OPND.push(num);
num =0;
}
}else{
switch (Precede(OPTR.top(),ch)){//比较OPTR的栈顶元素和ch的优先级
case '<':
OPTR.push(ch);//当前字符ch压入optr栈，读入下一个字符ch
cin >> ch;
break;
case '>':
theta = OPTR.top();OPTR.pop();//弹出OPTR栈顶元素符
b = OPND.top();OPND.pop();//弹出OPND栈顶的两个运算符
a= OPND.top();OPND.pop();
OPND.push(Operate(a,theta,b));//将运算结果压入OPND栈
break;
case '=':
OPTR.pop(); //OPTR的栈顶元素是"("且ch是")"
cin >> ch; //弹出OPTR栈顶的"(",读入下一字符ch
break;
default:
exit(ERROR);
}
}
}
cout << OPND.top();//求值结果
return 0;
}
完整代码
#include#include #define ERROR -1 using namespace std; //为实现运算符优先算法，可以使用两个工作栈 //一个OPTR:寄存运算符 //OPND:寄存操作数或运算结果 //In:判定读入的字符ch是否为运算符 //Precede 是判定运算符栈的栈顶元素与读入的元素负之间优先关系的函数 //Operate:为进行二元运算 bool In(char ch){ if(ch == '+' || ch=='-' || ch=='*' || ch=='/' || ch=='(' || ch==')' || ch=='#'){ return true; } return false; } char Precede(char ch1,char ch2){ if(ch1 =='+' || ch1 == '-'){ if(ch2 == '*' || ch2=='/' || ch2=='('){ return '<'; }else{ return '>'; } }else if(ch1 == '*' || ch1=='/'){ if(ch2 == '('){ return '<'; }else { return '>'; } }else if(ch1 == '('){ if(ch2==')'){ return '='; }else if(ch2 == '#'){ return 'E'; }else{ return '<'; } }else if(ch1 == ')'){ if(ch2=='('){ return 'E'; }else{ return '>'; } }else if(ch1 =='#'){ if(ch2=='#'){ return '='; }else if(ch2 == ')'){ return 'E'; }else{ return '<'; } } return 'E'; } int Operate(int a,char theta,int b){ if(theta == '+' ) return a+b; else if(theta == '-') return a-b; else if(theta == '*') return a*b; else if(theta == '/') return a/b; else return 0; } int main(){ //①初始化OPTR栈和OPND栈，将表达式起始负“#”压入OPTR栈 //②扫描表达式，读入第一个字符ch，如果表达式没有扫描完毕至"#"或OPTR的栈顶元素不为 // “#”则循环执行以下操作 //若ch不是运算符则压入OPND栈，读入下一个字符ch //若ch是运算符，则根据OPTR的栈顶元素和ch的优先级比较结果，做不同的处理 //若是小于，则ch压入optr栈，读入下一个字符ch //若是大于，则弹出optr栈顶的运算符，从OPND栈弹出两个数，进行相应运算，借故偶压入OPND栈， //若是等于，则optr的栈顶元素是“（”且ch是”）“这时弹出OPTR栈顶的”（“相当于括号匹配成功，然后读入下一个字符1ch //③ opnd栈顶元素即为表达式求值结果，返回此元素 stack OPND;//运算数栈 stack OPTR;//运算操符栈 OPTR.push('#');//表达式起始”#“压入OPTR栈 char ch; char theta; int a,b,num=0; cin >> ch; while(ch != '#' || OPTR.top()!='#'){ //表达式没有扫描完毕或OPTR的栈顶元素不为“#” if(!In(ch)){ //ch不是运算符则进OPND栈 num=num*10+(ch-'0'); cin >> ch; if(In(ch)) { OPND.push(num); num =0; } }else{ switch (Precede(OPTR.top(),ch)){//比较OPTR的栈顶元素和ch的优先级 case '<': OPTR.push(ch);//当前字符ch压入optr栈，读入下一个字符ch cin >> ch; break; case '>': theta = OPTR.top();OPTR.pop();//弹出OPTR栈顶元素符 b = OPND.top();OPND.pop();//弹出OPND栈顶的两个运算符 a= OPND.top();OPND.pop(); OPND.push(Operate(a,theta,b));//将运算结果压入OPND栈 break; case '=': OPTR.pop(); //OPTR的栈顶元素是"("且ch是")" cin >> ch; //弹出OPTR栈顶的"(",读入下一字符ch break; default: exit(ERROR); } } } cout << OPND.top();//求值结果 return 0; }
