栈的应用——中缀表达式转后缀表达式，后缀表达式的求值，中缀表达式求值

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <stack>
using namespace std;
int priority(char c)//比较优先级
{
    if(c=='*'||c=='/')
        return 2;
    if(c=='+'||c=='-')
        return 1;
    return 0;
}

int main()
{
    char str[105];
    scanf("%s",str);
    int len=strlen(str);
    stack<char> opt;
    for(int i=0;i<len;i++)
    {
        if(isalnum(str[i]))//为数字，直接入栈
        {
            while(i<len&&(isalnum(str[i])||str[i]=='.'))
            {
                cout<<str[i];
                i++;
            }
            i--;
            cout<<" ";
        }
        else if(str[i]=='(')//为左括号，直接入栈
                opt.push(str[i]);
        else if(str[i]==')')//为右括号，将栈顶元素出栈，直到碰到左括号
        {
            while(opt.top()!='(')
            {
                cout<<opt.top()<<" ";
                opt.pop();
            }
            opt.pop();//将左括号出栈
        }
        else if(opt.empty())//栈为空，将运算符直接入栈
        {
            opt.push(str[i]);
        }
        else
        {
            while(!opt.empty()&&priority(opt.top())>=priority(str[i]))//当栈不为空，并且栈顶元素的优先级大于等于当前元素
            {
                cout<<opt.top()<<" ";
                opt.pop();//将栈顶元素出栈
            }
            opt.push(str[i]);//将运算符入栈
        }
    }
    while(!opt.empty())//将栈中的剩余元素出栈
    {
        cout<<opt.top()<<" ";
        opt.pop();
    }
    cout<<endl;
    return 0;
}

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <stack>
#include <cctype>
#include <cstdlib>
using namespace std;
void compute(stack<double> &num,char opt)
{
    double x=num.top();
    num.pop();
    double y=num.top();
    num.pop();
    if(opt=='+')
        num.push(x+y);
    else if(opt=='-')
        num.push(y-x);
    else if(opt=='*')
        num.push(y*x);
    else
        num.push(y/x);
}
int main()
{
    char t[15];
    char str[105];
    stack<double> num;
    gets(str);
    int len=strlen(str);
    for(int i=0;i<len;++i)
    {
        if(str[i]==' ')
            continue;
        if(isalnum(str[i]))
        {
            memset(t,'\0',sizeof(t));
            int j=0;
            while(i<len&&(isalnum(str[i])||str[i]=='.')&&str[i]!=' ')
            {
                t[j]=str[i];
                ++j;
                ++i;
            }
            --i;
            num.push(atof(t));
        }
        else
        {
            compute(num,str[i]);
        }
    }
    cout<<num.top()<<endl;
    num.pop();
    return 0;
}

中缀表达式求值：

#include <stack>
#include <stdio.h>
#include <ctype.h>
#include <string.h>
#include <stdlib.h>

using namespace std;

int priority(char c)//优先级
{
    if(c == '=')    return 0;
    if(c == '+')    return 1;
    if(c == '-')    return 1;
    if(c == '*')    return 2;
    if(c == '/')    return 2;
    return 0;
}

void compute(stack<double>& Num,stack<char>& Op)//根据不同的运算符计算出两个数的值
{
    double b = Num.top();
    Num.pop();
    double a = Num.top();
    Num.pop();
    switch(Op.top())
    {
    case '+':
        Num.push(a+b);
        break;
    case '-':
        Num.push(a-b);
        break;
    case '*':
        Num.push(a*b);
        break;
    case '/':
        Num.push(a/b);
        break;
    }
    Op.pop();
}

int main()
{
    int z;
    char str[1005];
    stack<double> Num;
    stack<char> Op;
    scanf("%d",&z);
    while(z--)
    {
        scanf("%s",str);
        int len = strlen(str);
        for(int i=0; i<len; i++)
        {
            if(isdigit(str[i]))//如果是数字
            {
                double n = atof(&str[i]);
                while(i<len && (isdigit(str[i]) || str[i]=='.'))
                    i++;
                i--;
                Num.push(n);//将数字压入值栈
            }
            else
            {
                if(str[i] == '(')//如果是左括号
                    Op.push(str[i]);//直接入栈
                else if(str[i] == ')')//如果是右括号
                {
                    while(Op.top()!='(')//将运算符栈里面的运算符弹出来，直到为左括号结束
                        compute(Num,Op);//进行运算
                    Op.pop();//将左括号弹出
                }
                else if(Op.empty() || priority(str[i])>priority(Op.top()))//如果运算符栈为空或者当前运算符的优先级大于栈顶运算符的优先级，直接入栈
                    Op.push(str[i]);
                else
                {
                    while(!Op.empty() && priority(str[i])<=priority(Op.top()))//如果栈不为空且当前运算符的优先级小于或等于栈顶运算符的优先级，先将栈里面的运算符进行运算
                        compute(Num,Op);
                    Op.push(str[i]);//然后入栈
                }
            }
        }
        Op.pop();
        printf("%.2f\n",Num.top());
        Num.pop();
    }
    return 0;
}