欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

算法训练 表达式计算

程序员文章站 2022-06-26 08:34:51
...

算法训练 表达式计算

问题描述  
输入一个只包含加减乖除和括号的合法表达式,求表达式的值。其中除表示整除。
输入格式  
输入一行,包含一个表达式。
输出格式  
输出这个表达式的值。
样例输入
1-2+3*(4-5)
样例输出
-4
数据规模和约定 
表达式长度不超过100,表达式运算合法且运算过程都在int内进行。

#include<iostream>
#include<stack>
using namespace std;
stack<int> opnd;// 操作数栈
stack<char> optr;//运算符栈
int Level(char s)
{
    switch(s)//'+'<'-','*'<'/',因为从后往前算时,若先计算后面的加法或乘法,会导致计算错误
    {
    case '+':return 1;
    case '-':return 2;
    case '*':return 3;
    case '/':return 4;
    case '('://'('在栈内,优先级为0,在栈外,优先级为3
        if(optr.top()=='(')
            return 0;
        else
            return 5;
    }
    return 0;
}
char Compare(char *s)
{
    char t;
    if((*s==')'&&optr.top()=='(')||(*s=='\0'&&optr.top()=='\0'))
    {
        t='=';
    }
    else if(Level(*s)>Level(optr.top()))
    {
        t='>';
    }
    else if(Level(*s)==Level(optr.top()))
    {
        t='>';
    }
    else
    {
        t='<';
    }
    return t;
}
int ReadNumber(char *s)
{
    int temp=0,c=0;
    while(*s>='0'&&*s<='9')
    {
        temp=temp*10+*s-'0';
        s++;
        c++;
    }
    opnd.push(temp);
    return c;
}
void Calculate()//计算表达式的值,并将计算结果压入操作数栈;
{
    int t1,t2;
    t1=opnd.top();
    opnd.pop();
    t2=opnd.top();
    opnd.pop();
    switch(optr.top())
    {
    case '+':
    {
        opnd.push(t2+t1);
        break;
    }
    case '-':
    {
        opnd.push(t2-t1);
        break;
    }
    case '*':
    {
        opnd.push(t2*t1);
        break;
    }
    case '/':
    {
        opnd.push(t2/t1);
        break;
    }
    }
    optr.pop();//已经参与运算的运算符出栈
}
void Evaluate(char *s)
{
    optr.push('\0');// 头哨兵入栈
    while(!optr.empty())
    {
        if(*s>='0'&&*s<='9') //若当前字符为操作数
        {
            int t;
            t=ReadNumber(s);
            s+=t;
        }
        else// 当前*s为操作符
            switch(Compare(s))
            {
            case '>': // 操作符栈顶元素优先级小
            {
                optr.push(*s);//将*s压入操作符栈;
                s++;
                break;
            }
            case '=': // 操作符栈顶元素优先级等于*s
            {
                optr.pop();//弹出栈顶操作符; s++;
                s++;
                break;
            }
            case '<':  // 操作符栈顶元素优先级大
            {
                Calculate();//计算表达式的值,并将计算结果压入操作数栈;
                break;
            }
            s++;
            }
    }
}
int main(int argc, char*argv[])
{
    string str;
    cin>>str;
    str.push_back('\0');//string类最后不是以'\0'结尾,需手动添加
    Evaluate(&str[0]);
    cout<<opnd.top()<<endl;
}