栈的应用-简单计算器

/*
2*(3+4)
234+*

*/
#include<bits/stdc++.h>
using namespace std;
stack<char> s,s2;
string str,ret;
int priority(char c)
{
    if(c=='(') return 1;
    else if(c=='+') return 2;
    else if(c=='-') return 2;
    else if(c=='*') return 3;
    else if(c=='/') return 3;
    else if(c==')') return 4;
    else return -1;
}
void change(string str)
{
    int i=0;
    while(str[i]!='\0'){
        if(str[i]>='0'&&str[i]<='9'){
            ret+=str[i];
        }
        else if(str[i]=='(')
        {
            s.push(str[i]);
        }
        else if(str[i]==')')
        {
            while(s.top()!='(')
            {
                ret+=s.top();
                s.pop();
            }
            if(s.top()=='(')
                s.pop();
        }
        else if(s.empty() || priority(str[i]) > priority(s.top()))
        {
            s.push(str[i]);
        }
        else{
            while(priority(str[i])<=priority(s.top()))
            {
                ret+=s.top();
                s.pop();
            }
            s.push(str[i]);
        }
        i++;
    }
    while(!s.empty())
    {
        ret+=s.top();
        s.pop();
    }
}

int cal(string ret)
{
    int i=0;
    while(ret[i]!='\0')
    {
        if(ret[i]>='0'&&ret[i]<='9')
        {
            s2.push(ret[i]);
        }
        else if(ret[i]=='+')
        {
            int a=s2.top()-'0';
            s2.pop();
            int b=s2.top()-'0';
            s2.pop();
            s2.push(a+b+'0');

        }
        else if(ret[i]=='-')
        {
            int a=s2.top()-'0';
            s2.pop();
            int b=s2.top()-'0';
            s2.pop();
            s2.push(b-a+'0');

        }
        else if(ret[i]=='*')
        {
            int a=s2.top()-'0';
            s2.pop();
            int b=s2.top()-'0';
            s2.pop();
            s2.push(a*b+'0');

        }
        else if(ret[i]=='/')
        {
            int a=s2.top()-'0';
            s2.pop();
            int b=s2.top()-'0';
            s2.pop();
            s2.push(b/a+'0');

        }
        i++;
    }
    return s2.top()-'0';
}
int main()
{
    cin >> str;
    change(str);
    cout << ret << endl;
    cout << cal(ret) << endl;
    return 0;
}

理论分析：

数据结构–中缀表达式转为后缀表达式（逆波兰表达式）

中缀表达式是一个通用的算术或逻辑公式表示方法。操作符是以中缀形式处于操作数中间。例如:3*4+3-1;

后缀表达式不包含括号，运算符放在两个运算对象的后面，所有的计算按运算符出现的顺序，严格从左向右（不再考虑运算符的优先规则）例如：(2+1)*3,即2 1 + 3 *

（以上来自百度百科）

具体的代码实现：代码实现中缀转后缀表达式

1.中缀表达式转为后缀表达式

想要完成此过程需要一个数组arr存放中缀表达式，一个ret 存放后缀表达式，还要借助一个辅助栈stack1存放操作符,stack2存放运算结果。

规则：

从左到右一次遍历中缀表达式，如果是数字就直接存放到后缀表达式中;

如果是操作符，例如操作符A，需要将A于操作符栈stack1的栈顶操作符比较，如果stack1为空或栈顶操作符优先级低于A，将A压入stack1.

如果A的优先级低于或等于stack1栈顶的操作符的优先级，把栈顶操作符pop出栈，存到ret 中，然后继续与A比较，重复此前动作直到A入栈。

注意：

操作符’(‘和’)’ 比较特殊。如果是’(’ 直接入栈stack1;如果是‘)’ 需要将stack1的操作符pop到ret中，直到弹出’(’；

重复以上工作，直到把操作符栈stack1中的操作符全部弹出到ret中；这样就把中缀表达转化为后缀表达式；

例如：

中缀表达式：3*1+(4+6)/2-1

第一步：取3，ret[ 3 ] , stack1[ ];

第二步：取*， ret[3] , stack1 [ * ];

第三步: 取1 ，ret[3，1] , stack1 [ * ];

第四步，取+，ret[3，1，*] , stack1 [ + ];

第五步：取(, ret[3，1，*] , stack1 [ + ,( ];

第六步：取4， ret[3，1，*，4] , stack1 [ + ,( ];

第七步：取+， ret[3，1，*，4] , stack1 [ + ,( ,+ ];

第八步：取6，ret[3，1，*，4, 6] , stack1 [ + ,( ,+ ];

第九步：取), ret[3，1，*，4, 6,+] , stack1 [ + ];

第十步：取/, ret[3，1，*，4, 6,+] , stack1 [ + ,/ ];

第十一步：取2，ret[3，1，*，4, 6,+，2] , stack1 [ + ,/ ];

第十二步：取-， ret[3，1，*，4,6,+，2，/, + ] , stack1 [ - ];

第十三步：取1，ret[3，1，*，4,6,+，2，/，+,1 ] , stack1 [ - ];

处理stack1： ret[3，1，*，4, 6,+，2，/， +,1 ,- ] , stack1 [ ];

所以后缀表达式为:3，1，*，4, 6,+，2，/， +,1 ,- ;

2.利用后缀表达式计算结果

规则：遍历储存后缀表达式的列表，将元素依次进栈，当遇到操作符时，连续出栈两个元素，进行运算，再将结果进栈，最后栈内留下的元素就是计算结果