栈应用之：表达式求值
<font color="#dd0000">栈应用之：表达式求值</font>
题目描述：
算数四则运算的规则是1）先乘除，后加减；2）从左算到右；3）先括号内，后括号外。
由此，算式4+23-10/5的计算顺序为4+23-10/5=4+6-10/5=4+6-2=8。
给定一个以“#”作为结束符的算式，求出算式的结果。
输入
以“#”结尾的表达式，运算数为正整数。每个表达式占一行。
输出
输出表达式运算的结果。
样例输入
4+23-10/5#
3(7-2)#
2*3/2#
样例输出
8
15
3
<font color="#dd0000">题解：</font><br /> 这道题可是磨了我几天啊，开始就不知道怎么确定各个运算符之间的优先关系，由于我们学的数据结构教材和题目所说的严蔚敏《数据结构（C语言）》不一样，导致开始不知如何下手，于是在网上看了大佬的博客，发现了用个二维数组即可（只能说自己太菜了--_--）
<font color="#dd0000">其中θ1为存放运算符的栈（我自己定义的为s2）的栈顶元素，θ2为从表达式中读取的操作符</font><br />
于是就开始一顿猛操作，直接用C++的STL模拟，于是就开始了一直WA，一直爽的漫长过程！！！
开始不能静下心来debug，导致一直没找到自己的错误，今天中午乘着下午没课，又打算再来调试调试，于是发现了在运算时没有考虑位置（比如：在除时，分子分母位置居然弄反了；减法也就一样了）<font color="#dd0000">tcl</font><br />
后面又继续，到处设中间数据，由于吃了个午饭，看了会电视，偷了下懒就去睡觉了，醒来继续肝，发现已经离成功不远了，最后终于发现原来在判断s2的栈顶大于s[i]时，没有实现让s[i]继续循环<font color="#dd0000">居然没有break</font><br />
代码如下：
#include<cstdio>
#include<cstring>
#include<stack>
#include<iostream>
using namespace std;
char s[10010];
stack<double>s1; //偷了下懒，利用的C++中的STL模拟，用来存放数值
stack<char>s2; //同上，用来存放运算符
const char priority[7][7]= //确定运算符之前的优先级
{
{'>','>','<','<','<','>','>'},
{'>','>','<','<','<','>','>'},
{'>','>','>','>','<','>','>'},
{'>','>','>','>','<','>','>'},
{'<','<','<','<','<','=','0'},
{'>','>','>','>','0','>','>'},
{'<','<','<','<','<','0','='},
};
int getIndex(char c) //确定两个运算符之间在二维数组对应的行和列
{
int index;
switch(c)
{
case'+':
index=0;
break;
case'-':
index=1;
break;
case'*':
index=2;
break;
case'/':
index=3;
break;
case'(':
index=4;
break;
case')':
index=5;
break;
default:
index=6;
break;
}
return index;
}
char getPriority(char a,char b) //确定s2栈顶元素与s[i]的优先级
{
int index1,index2;
index1=getIndex(a);
index2=getIndex(b);
//printf("%d %d\n",index1,index2);
return priority[index1][index2];
}
double calculate(double num1,char c,double num2) //计算，重点注意num2和num1千万别反了
{
double Num;
switch(c)
{
case'+':
Num=num2+num1;
break;
case'-':
Num=num2-num1;
break;
case'*':
Num=num2*num1;
break;
case'/':
Num=num2/num1;
break;
}
return Num;
}
double getAnswer(char s[]) //主要函数
{
s2.push('#'); //提前处理s2，让一个优先级最小的字符入栈
int counter=0;
int len=strlen(s);
int i=0;
while(i<len)
{
if(s[i]-'0'>=0&&s[i]-'0'<=9) //如果是数字
{
if(counter==1) //如果是多位数的情况
{
double num1=s1.top();
s1.pop();
num1=num1*10+(s[i]-'0');
s1.push(num1);
i++;
}
else //一位数的情况
{
s1.push(s[i]-'0');
i++;
counter++;
}
}
else
{
counter=0;
//cout<<s2.top()<<s[i];
char c=getPriority(s2.top(),s[i]); //判断优先级
//cout<<c<<' ';
switch(c)
{
case'<': //s2栈顶元素小于当前运算符，当前运算符直接进栈
s2.push(s[i]);
i++;
break;
case'>': //关键，直到s2栈顶元素小于当前运算符为止
{
char c1=s2.top();
//cout<<c1<<endl;
s2.pop();
//cout<<s[i]<<endl;
//cout<<s2.top()<<endl;
double num2=s1.top();
//cout<<num2<<' ';
s1.pop();
double num3=s1.top();
//cout<<num3<<' ';
s1.pop();
double num4=calculate(num2,c1,num3);
//cout<<num4<<endl;
s1.push(num4);
//cout<<i<<endl;
break; //千万别少了
}
case'=':
s2.pop();
i++;
break;
}
}
}
//cout<<s1.top()<<endl;
return s1.top();
}
int main()
{
while(~scanf("%s",s))
{
while(!s1.empty()) //将上一个的数据清空
s1.pop();
while(!s2.empty()) //同上
s2.pop();
double num=getAnswer(s);
cout<<num<<endl;
}
return 0;
}
自闭了
后面自己还是试着用数组模拟栈，自己手写了下栈，而没有用STL
代码如下：
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
char s[100010];
typedef struct
{
double data[100010];
int top;
}seq1;
seq1 s1;
typedef struct
{
char data[100010];
int top;
}seq2;
seq2 s2;
char priority[7][7]=
{
{'>','>','<','<','<','>','>'},
{'>','>','<','<','<','>','>'},
{'>','>','>','>','<','>','>'},
{'>','>','>','>','<','>','>'},
{'<','<','<','<','<','=','0'},
{'>','>','>','>','0','>','>'},
{'<','<','<','<','<','0','='},
};
int getIndex(char c)
{
int index;
switch(c)
{
case '+':index=0;break;
case '-':index=1;break;
case '*':index=2;break;
case '/':index=3;break;
case '(':index=4;break;
case ')':index=5;break;
default:index=6;break;
}
return index;
}
char getPriority(char a,char b)
{
int index1=getIndex(a);
int index2=getIndex(b);
return priority[index1][index2];
}
double calculate(double num2,char c,double num1)
{
double num;
switch(c)
{
case '+':num=num2+num1;break;
case '-':num=num2-num1;break;
case '*':num=num2*num1;break;
case '/':num=num2/num1;break;
}
return num;
}
double getAnswer(char s[])
{
s2.top++;
s2.data[s2.top]='#';
int counter=0;
int len=strlen(s);
int i=0;
while(i<len)
{
if(s[i]-'0'>=0&&s[i]-'0'<=9)
{
if(counter==1)
{
double t=s1.data[s1.top];
s1.top--;
t=t*10+(s[i]-'0');
s1.top++;
s1.data[s1.top]=t;
i++;
}
else
{
s1.top++;
s1.data[s1.top]=(s[i]-'0');
counter++;
i++;
}
}
else
{
counter=0;
char ch=getPriority(s2.data[s2.top],s[i]);
switch(ch)
{
case '<':s2.top++;s2.data[s2.top]=s[i];i++;break;
case '>':
{
char c=s2.data[s2.top];
s2.top--;
double num1=s1.data[s1.top];
s1.top--;
double num2=s1.data[s1.top];
s1.top--;
double Num=calculate(num2,c,num1);
s1.top++;
s1.data[s1.top]=Num;
break;
}
case '=':
s2.top--;
i++;
break;
}
}
}
return s1.data[s1.top];
}
int main()
{
while(~scanf("%s",s))
{
s1.top=-1;
s2.top=-1;
double num;
num=getAnswer(s);
printf("%d\n",(int)num);
}
return 0;
}
————————————————————————————————————————————
此处有分隔符
————————————————————————————————————————————
在学期末课程设计中，也是选的这个课题，于是除上面题目的简单要求外，进行了进一步的拓展：
实现了算术、关系、逻辑、以及三者之间综合计算
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>
#define Maxsize 1000
/**
浮点数大小之间判断允许误差范围
*/
const double EPS=1e-6;
/**
定义数值栈结构
*/
struct
{
double data[Maxsize];
int top;
} S1;
/**
定义运算符栈结构
*/
struct
{
char data[Maxsize];
int top;
} S2;
char s[Maxsize]; //输入的表达式
/**
通过二维数组判断运算符之间的优先级
其中'0'表示该种关系不存在会出现
*/
char priority[20][20]=
{
{'>','>','>','>','>','>','>','<','>','>','>','>','>','>','>','>','>','>'}, //'!'
{'<','>','>','<','<','<','<','<','>','>','>','>','>','>','>','>','>','>'}, //'+'
{'<','>','>','<','<','<','<','<','>','>','>','>','>','>','>','>','>','>'}, //'-'
{'<','>','>','>','>','<','>','<','>','>','>','>','>','>','>','>','>','>'}, //'*'
{'<','>','>','>','>','<','>','<','>','>','>','>','>','>','>','>','>','>'}, //'/'
{'<','>','>','>','>','>','>','<','>','>','>','>','>','>','>','>','>','>'}, //'^'
{'<','>','>','<','<','<','<','<','>','>','>','>','>','>','>','>','>','>'}, //'%'
{'<','<','<','<','<','<','<','<','=','<','<','<','<','<','<','<','<','0'}, //'('
{'>','>','>','>','>','>','>','0','>','>','>','>','>','>','>','>','>','>'}, //')'
{'<','<','<','<','<','<','<','<','>','>','>','>','>','>','>','>','>','>'}, //'>'
{'<','<','<','<','<','<','<','<','>','>','>','>','>','>','>','>','>','>'}, //'<'
{'<','<','<','<','<','<','<','<','>','>','>','>','>','>','>','>','>','>'}, //'>='
{'<','<','<','<','<','<','<','<','>','>','>','>','>','>','>','>','>','>'}, //'<='
{'<','<','<','<','<','<','<','<','>','>','>','>','>','>','>','>','>','>'}, //'=='
{'<','<','<','<','<','<','<','<','>','>','>','>','>','>','>','>','>','>'}, //'!='
{'<','<','<','<','<','<','<','<','>','<','<','<','<','<','<','>','>','>'}, //'&&'
{'<','<','<','<','<','<','<','<','>','<','<','<','<','<','<','>','>','>'}, //'||'
{'<','<','<','<','<','<','<','<','0','<','<','<','<','<','<','<','<','='}, //'#'
};
/**
获取运算符对应于二维数组行、列的函数
*/
int getIndex(char ch)
{
int index;
switch(ch)
{
case '!':
index=0;
break;
case '+':
index=1;
break;
case '-':
index=2;
break;
case '*':
index=3;
break;
case '/':
index=4;
break;
case '^':
index=5;
break;
case '%':
index=6;
break;
case '(':
index=7;
break;
case ')':
index=8;
break;
case '>':
index=9;
break;
case '<':
index=10;
break;
case 'X':
index=11;
break;
case 'Y':
index=12;
break;
case 'Z':
index=13;
break;
case 'W':
index=14;
break;
case '&':
index=15;
break;
case '|':
index=16;
break;
case '#':
index=17;
break;
}
return index;
}
/**
获取两运算符之间优先级函数
*/
char getPriority(char a,char b)
{
int index1=getIndex(a);
//printf("index1=%d\n",index1);
int index2=getIndex(b);
//printf("index2=%d\n",index2);
//printf("index1=%d,index2=%d\n",index1,index2);
return priority[index1][index2];
}
/**
直接计算函数
*/
double calculate(double num1,char c,double num2)
{
double Num;
switch(c)
{
case '+':
{
Num=num2+num1;
break;
}
case '-':
{
Num=num2-num1; //注意原来在栈1的相对位置
break;
}
case '*':
{
Num=num2*num1;
break;
}
case '/':
{
Num=num2/num1;
//printf("num2/num1=%.2f\n",Num);
break;
}
case '^':
{
Num=pow(num2,num1);
break;
}
case '%':
{
Num=fmod(num2,num1); //便于小数间取余
break;
}
case '>':
{
if(num2>num1+EPS) //浮点数大小判断
Num=1;
else
Num=0;
//printf("Num=%d\n",(int)Num);
break;
}
case '<':
{
if(num2<(num1-EPS))
Num=1;
else
Num=0;
break;
}
case 'X':
{
if(num2>=(num1+EPS))
Num=1;
else
Num=0;
break;
}
case 'Y':
{
if(num2<=(num1-EPS))
Num=1;
else
Num=0;
break;
}
case 'Z':
{
if(fabs(num2-num1)<=EPS)
Num=1;
else
Num=0;
break;
}
case 'W':
{
if(fabs(num2-num1)>EPS)
Num=1;
else
Num=0;
//printf("Num=%d\n",(int)Num);
break;
}
case '&':
{
if(num2!=0&&num1!=0)
Num=1;
else
Num=0;
//printf("num1=%d num2=%d Num=%d\n",(int)num1,(int)num2,(int)Num);
break;
}
case '|':
{
if(num1==0&&num2==0)
Num=0;
else
Num=1;
break;
}
}
//printf("Num=%.2f\n",Num);
return Num;
}
/**
主要运算函数
*/
double getAnswer(char s[])
{
/**
初始化栈2，便于运算符之间比较
*/
S2.top++;
S2.data[S2.top]='#';
int len=strlen(s);
int i=0;
int counter=0; //计数器，数字有一位和多位数字的形式
int flag=0; //小数标记器
while(i<len)
{
/**
小数点
*/
if(s[i]=='.')
{
flag=1;
counter=0;
i++;
}
/**
如果是是数值则进栈1
*/
if(s[i]>='0'&&s[i]<='9')
{
/**
小数情况
*/
if(flag==1)
{
if(counter==0)
{
double t=S1.data[S1.top];
S1.top--;
t=t+0.1*(s[i]-'0');
//printf("t=%.2f\n",t);
S1.top++;
S1.data[S1.top]=t;
counter++;
i++;
}
else
{
int m=counter+1; //表示该数字为小数点后第几位
double t=S1.data[S1.top];
S1.top--;
t=t+pow(0.1,m)*(s[i]-'0');
//printf("t=%.2f\n",t);
S1.top++;
S1.data[S1.top]=t;
counter++;
i++;
}
}
else
{
if(counter==0)
{
S1.top++;
S1.data[S1.top]=s[i]-'0'; //进栈，并将字符型转化为整形
i++;
counter++;
}
/**
多位数进栈
*/
else
{
/**原栈顶元素出栈*/
double t=S1.data[S1.top];
//printf("t=%.2f\n",t);
S1.top--;
t=t*10+(s[i]-'0');
/**替换栈顶元素*/
S1.top++;
S1.data[S1.top]=t;
//printf("S1.data[S1.top]=%.2f\n",S1.data[S1.top]);
counter++;
i++;
}
}
}
/**
如果是运算符则进栈2
*/
else
{
counter=0; //计数器归零
flag=0; //小数标记器为0
char ch=getPriority(S2.data[S2.top],s[i]);
//printf("%c\n",ch);
switch(ch)
{
case '<':
{
/**
运算符直接进栈
*/
S2.top++;
S2.data[S2.top]=s[i];
i++; //继续访问
break;
}
case '>':
{
/**
当前运算符栈栈顶元素出栈
*/
char c=S2.data[S2.top];
S2.top--;
/**
如果是!(即 非 逻辑符时,则只需数值栈出栈一次即可)
*/
if(c=='!')
{
double num1=S1.data[S1.top];
S1.top--;
if(num1!=0)
{
S1.top++;
S1.data[S1.top]=0;
}
else
{
S1.top++;
S1.data[S1.top]=1;
}
}
/**
如果是其他符号时，数值栈连续出栈两次
*/
else
{
double num1=S1.data[S1.top];
S1.top--;
double num2=S1.data[S1.top];
S1.top--;
/**
计算新的数值然后入栈S1
*/
double Num=calculate(num1,c,num2);
//printf("Num=%f\n",Num);
S1.top++;
S1.data[S1.top]=Num;
}
break;
}
case '=':
{
S2.top--;
i++; //继续访问
break;
}
}
}
}
return S1.data[S1.top];
}
/**
程序声明
*/
void status()
{
printf("*----------------------------------------------------------------*\n");
printf("* 请输入你想要进行的操作 *\n");
printf("* *\n");
printf("* 1.算术表达式计算 *\n");
printf("* *\n");
printf("* 2.关系表达式计算 *\n");
printf("* *\n");
printf("* 3.逻辑表达式计算 *\n");
printf("* *\n");
printf("* 0.退出该程序 *\n");
printf("* *\n");
printf("*----------------------------------------------------------------*\n");
printf("\n");
}
/**
主函数
*/
int main()
{
printf("*-----------------该程序可以实现基本表达式的计算-----------------*\n");
status();
int n;
while(~scanf("%d",&n))
{
switch(n)
{
case(1):
{
printf("请输入算术表达式（以'#'表示结束）:\n");
scanf("%s",s);
S1.top=-1;
S2.top=-1;
double num; //最终结果
num=getAnswer(s);
printf("该算术表达式结果为:\n%.3f\n",num);
printf("*----------------------------请继续操作--------------------------*\n");
printf("\n");
status();
break;
}
case (2):
{
printf("请输入关系表达式（其中 >= 用X表示, <= 用Y表示, == 用Z表示, != 用W表示,以'#'表示结束）:\n");
scanf("%s",s);
double num=getAnswer(s);
//printf("num=%lf\n",num);
int flag=(int)num;
//printf("flag=%d\n",flag);
if(flag==1)
{
printf("该关系表达式结果为:\nTURE\n");
}
else
{
printf("该关系表达式结果为:\nFLASE\n");
}
printf("*----------------------------请继续操作--------------------------*\n");
printf("\n");
status();
break;
}
case (3):
{
printf("请输入逻辑表达式（ && 用'&'表示, || 用'|'表示,以'#'表示结束）:\n");
scanf("%s",s);
double num=getAnswer(s);
int flag=(int)num;
//printf("flag=%d\n",flag);
if(flag==1)
{
printf("该逻辑表达式结果为:\nTRUE\n");
}
else
printf("该逻辑表达式结果为:\nFALSE\n");
printf("*----------------------------请继续操作--------------------------*\n");
printf("\n");
status();
break;
}
case (0):
{
printf("*----------------------------------------------------------------*\n");
printf("* *\n");
printf("* 程序结束，谢谢使用! *\n");
printf("* *\n");
printf("*----------------------------------------------------------------*\n");
return 0;
}
}
}
return 0;
}
/**
sample1（算术表达式） :
(0.25*2+8)/5# 1.7 //实数类型
7.25*2-8.3# 6.2 //实数类型
3.2^3-1.33# 31.438 //实数类型
2*3-9/4+4*3/2# 9.75 //实数类型
(15/3-8)*3# -9 //答案负数
(9-9)/8# 0 //答案为0
2^20-512*4# 1046528 //幂指数较大时
(3-1)^4+5*2-16# 10 //多种运算符
(2^3-5)/3+10# 11 //一重括号类型
2*(6+2*(3+6*(6+6)))# 312 //多重括号类型
((2+2)^2-5)%5# 1 //取余运算
2^6%9# 1 //取余运算
(4.5%3.3)/3# 0.4 //小数取余
*/
/**
sample2（关系表达式）:
6*3+18X34# TURE //(其中 X 表示 >= )
10^2-9^2Y8^2-2^2# TURE //(其中 Y 表示 <= )
4*8-25>5*2+1# FLASE //
2.26^5<2*5# FALSE //
(30-28)*10Z4*5# TURE //(其中 Z 表示 == )
5^2W20+5# FLASE //(其中 W 表示 != )
*/
/**
sample3（逻辑表达式）:
!(1+4^2.3)|0# FALSE //基本逻辑表达式 (其中 | 表示 || )
((8.23+2)/3)|(4.35%2.54)# TURE //基本逻辑表达式求值（其中 | 表示 || ）
5%2*4>5|4%2*5<7# TURE //算术、关系、逻辑表达式综合计算
(2^3*5>38)&(4-13+3^2)# FALSE //算术、关系、逻辑表达式综合计算
*/
投递华为等公司10个岗位 >