前言
运用堆栈解决表达式的求值，代码思路为：
1.定义两个栈，一个char类型的栈用于存放运算符(ysf)一个int类型的栈用于存放操作数(czs)
如一个表达式3+6*9，将“+”，“*”入ysf栈，将“3”“6”“9”入czs栈
2.运用getchar进行数据的录入，如果接收的是运算符，将其插入到运算符栈中，如果接收的是数字字符，则将其插入至操作数栈中，注意这里接收的是字符而不是数字，将字符转为数字需用x-‘0’
3.运算符间进行优先级的比较
如上表（转自清华大学出版社数据结构与算法），运算符1的优先级与运算符2的优先级进行比较，使其返回“<”或“>”，遇到<则将运算符入栈，然后接着取下一个字符，遇到>则调取操作数进行运算，而要完成从栈顶循环运算至栈底的目的，则需在运算符栈底先插入一个“#”，然后默认插入结束后再插入一个“#”如图：
文章来源地址https://www.toymoban.com/news/detail-861704.html
例子：ysf（运算符）栈中第一个默认为“#”，首先插入一个“+”，由表3.1可知“#”比“+” 等于“<”，所以将“+”入栈，栈顶元素现在为“+”，第二次插入“*”，“+”比“*”等于“<”，将“*”入栈，此时表达式结束
默认在结尾插入一个“#”，所以现在ysf栈中的元素由下至上为“#”，“+”，“*”，“#”四个元素，然后接着进行运算符优先级的比较，栈顶的“#”比“*”等于“>”所以取操作数进行计算，弹出“#”，现在栈顶元素为“*”，然后栈顶的“*”比“+”等于“>”，然后接着去操作数进行计算，依次类推，直到最后栈顶元素为“#”，程序结束。
第一步：运算符优先级表
int getindex(char c)//获取运算符所对应的索引
{
int index;
if(c=='+')
{
index = 0;
}
else if (c == '-')
{
index = 1;
}
else if (c == '*')
{
index = 2;
}
else if (c == '/')
{
index = 3;
}
else if (c == '(')
{
index = 4;
}
else if (c == ')')
{
index = 5;
}
else if (c == '#')
{
index = 6;
}
else
{
index = 9;
}
return index;
}
char reindex(int a,int b)//运算符优先级表，将索引转化为“>”,“<”
{
char index[7][7] =
{
{'>','>','<','<','<','>','>'},
{'>','>','<','<','<','>','>'},
{'>','>','>','>','<','>','>'},
{'>','>','>','>','<','>','>'},
{'<','<','<','<','<','=',' '},
{'>','>','>','>',' ','>','>'},
{'<','<','<','<','<',' ','='}
, };
if (a < 7 && b < 7)
{
return index[a][b];
}
else
{
return '0';
}
}
返回结果是“>”或“<”
第二步：具体运算
void get()
{
int can=1,a=1,b = 1;
char cz;
ysf.push('#');
int count = 0;
char c = getchar();
while ((c != '#' || ysf.top() != '#')&&can)//防止为空
{
//if(c=='\n'){c = '#';}//取消‘#’的限制条件；
can = 1;
if (c >= '0' && c <= '9')
{
if (count == 1)
{
a = czs.top();
czs.pop();
czs.push(a * 10 + (c - '0'));
count = 1;
}
else
{
czs.push(c - '0');
count++;
}
c = getchar();
}
else
{
count = 0;
switch (reindex(getindex(ysf.top()), getindex(c)))
{
case'<':
ysf.push(c);
c = getchar();
break;
case'=':
ysf.pop();
c = getchar();
break;
case'>':
cz = ysf.top();
ysf.pop();
a = czs.top();
czs.pop();
b = czs.top();
czs.pop();
czs.push(ys(a, cz, b));
break;
case'0':
{
can = 0;
break;
}
}
}
}
if (can == 1)
{
cout << czs.top();
}
else if (can == 0)
{
cout << "格式错误";
}
}
总代码
#include<iostream>
#include<stack>
using namespace std;
stack<char> ysf;
stack<int>czs;
int getindex(char c)
{
int index;
if(c=='+')
{
index = 0;
}
else if (c == '-')
{
index = 1;
}
else if (c == '*')
{
index = 2;
}
else if (c == '/')
{
index = 3;
}
else if (c == '(')
{
index = 4;
}
else if (c == ')')
{
index = 5;
}
else if (c == '#')
{
index = 6;
}
else
{
index = 9;
}
return index;
}
char reindex(int a,int b)
{
char index[7][7] =
{
{'>','>','<','<','<','>','>'},
{'>','>','<','<','<','>','>'},
{'>','>','>','>','<','>','>'},
{'>','>','>','>','<','>','>'},
{'<','<','<','<','<','=',' '},
{'>','>','>','>',' ','>','>'},
{'<','<','<','<','<',' ','='}
, };
if (a < 7 && b < 7)
{
return index[a][b];
}
else
{
return '0';
}
}
int ys(int a, char cz, int b)
{
switch (cz)
{
case'+':
return a + b;
case'-':
return b - a;//栈的先进后出
case'*':
return a * b;
case'/':
return b / a;//too
default:
break;
}
}
void get()
{
int can=1,a=1,b = 1;
char cz;
ysf.push('#');
int count = 0;
char c = getchar();
while ((c != '#' || ysf.top() != '#')&&can)//防止为空
{
//if(c=='\n'){c = '#';}//取消‘#’的限制条件；
can = 1;
if (c >= '0' && c <= '9')
{
if (count == 1)
{
a = czs.top();
czs.pop();
czs.push(a * 10 + (c - '0'));
count = 1;
}
else
{
czs.push(c - '0');
count++;
}
c = getchar();
}
else
{
count = 0;
switch (reindex(getindex(ysf.top()), getindex(c)))
{
case'<':
ysf.push(c);
c = getchar();
break;
case'=':
ysf.pop();
c = getchar();
break;
case'>':
cz = ysf.top();
ysf.pop();
a = czs.top();
czs.pop();
b = czs.top();
czs.pop();
czs.push(ys(a, cz, b));
break;
case'0':
{
can = 0;
break;
}
}
}
}
if (can == 1)
{
cout << czs.top();
}
else if (can == 0)
{
cout << "格式错误";
}
}
int main()
{
get();//()记得用英文输入法；
return 0;
}
文章来源：https://www.toymoban.com/news/detail-861704.html
到了这里，关于数据结构之表达式求值的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
