数据结构实验1算术表达式

表达式中相邻两个运算符的计算次序是优先级高的先计算,若优先级相同,则自左而右计算。使用括号时从最内层括号开始计算。R1,R2,R3为中间计算结果。

在计算表达式值的过程中,需要开设两个栈:

1)运算符栈op存储运算符。

2)数值栈val:存储操作数和中间运算结果。若表达式中无优先级最高的单目算符,则操作数或中间运算结果直接压入val栈,否则操作数或者中间运算结果入栈前需要分析op栈顶有多少个连续的单目运算符。这些单目运算符出op栈,并连续对操作数进行相应的单目运算,最后将运算结果压人val栈.

计算表达式的基本思想是顺序扫描表达式的每个字符,·若是操作数。则慢作数压入val栈。

1若是操作数,入栈

2 若是运算符,<op>,则计算op栈顶中优先级比op高的双目算符op1..opk弹出这些双目运算符,每弹出一个双目运算符opi(1<=i<=k),则从val栈中退出两个操作数ab形成运算指令a<opi>b,并将结果重新压人val栈。进行完op1,..opk的运算后,op压人运算符栈op,

 扫描完表达式的所有字符后,若运算符栈op不空,则栈中的运算符相继出栈。每弹出一个运算符,从val栈中退出两个操作数,进行相应运算后的结果重新压人val栈。最后val栈的栈顶元素是表达式的值.

#include<cstdio>
#include<cstring>
#include<stack>
using namespace std;
char oper[6]={'+','-','*','/','(',')'};
//the stand operation:priority;standop[i][j],the current op is j,and i is the pre.
//1:>:i>j 0:=:i=j
int standop[6][6]={
{ 1,1,-1,-1,-1,1},
{ 1,1,-1,-1,-1,1},
{1,1,1,1,-1,1},
{1,1,1,1,-1,1},
{-1,-1,-1,-1,-1,-1},
{ 1,1,1,1,0,1}};
stack <int> num;
stack <char> op;
int findtheop(char x){
    for(int i=0;i<7;i++){
        if(oper[i]==x)return i;
    }
    return -1;
}
int priority(char opera1,char opera2){
    //the priority of the operator between current and the before
    return standop[findtheop(opera1)][findtheop(opera2)];
}
int calc(int a,char opera,int b){
    switch(opera){
        case '+':return a+b;
        case '-':return a-b;
        case '*':return a*b;
        case '/':return a/b;
    }
    return 0;
}
int calc2(){
    int x2=num.top();
    num.pop();
    int x1=num.top();
    num.pop();
    num.push(calc(x1,op.top(),x2));
//    printf("x1 %d  x2%d  ans %d\n",x1,x2,num.top());
    op.pop();
}
void judge(char opera){
    if(op.empty()|| opera=='('){op.push(opera);return;}
    while(!op.empty() && priority(op.top(),opera)>0){
        if(opera==')'){
            while(op.top()!='(')calc2();
            if(op.top()=='(')op.pop();
            return;
        }else
        calc2();
    }
    op.push(opera);
}
void init(){
    while(!op.empty())op.pop();
    while(!num.empty())num.pop();
    char a;
    while(scanf("%c",&a)&& a!='#'){
        if(a>47 && a<58){
            char x;
            int t=a-48;
            while(scanf("%c",&x)&& x>47 && x<58){
                t=t*10+x-48;
            }
            num.push(t);
            if(x=='#')break;
            judge(x);
        }
        else{
            judge(a);
        }
    }
    while(!op.empty()){
//        printf("op%c   \n",op.top());
        calc2();
    }
}
int main(){
    init();
    printf("%d",num.top());

}
 

 

没加注释,不明吧的留言。给学弟学妹的福利。还有一些在随意coding–》课程设计里或者算法学习里

文章版权归 FindHao 所有丨本站默认采用CC-BY-NC-SA 4.0协议进行授权|
转载必须包含本声明,并以超链接形式注明作者 FindHao 和本文原始地址:
https://www.findhao.net/easycoding/263

你可能喜欢:(相似内容推荐和广告都使用了谷歌的推荐系统,需要对本站取消广告屏蔽才能显示。感谢点击↓广告支持博主~)

Find

新浪微博(FindSpace博客)QQ群:不安分的Coder(375670127) 不安分的Coder

发表评论

电子邮件地址不会被公开。 必填项已用*标注

*