中缀表达式转后缀表达式，及含多位负数的中缀表达式计算（中缀转后缀解法）

中缀转后缀步骤（来自这里）：

1).初始化两个栈：运算符栈s1和存储中间结果的栈s2；

　　　　2).从左到右扫描中缀表达式；

　　　　3).遇到操作数时，将其压入s2;

　　　　4).遇到运算符时，比较其与s1栈顶运算符的优先级；

　　1.如果s1为空，或栈顶运算符为左括号"("，则直接将此运算符入栈

　　2.否则，若优先级比栈顶运算符的高，也将运算符压入s1

　　3.否则，将s1栈顶的运算符弹出并压入s2中，再次转到(4-1)与s1中新的栈顶运算符相比较；

　　　　5)遇到括号时：

　　　　　　(1)如果时左括号"("，则直接压入s1

　　　　　　(2)如果是右括号")"，则依次弹出s1栈顶的运算符，并压入s2,直到遇到左括号为止，此时将这一对括号丢弃

　　　　6)重复2至5,直到表达式的最右边

　　　　7)将s1中剩余的运算符依次弹出并压入s2

　　　　8）依次弹出s2中的元素并输出，结果的逆序为中缀表达式对应的后缀表达式

单单得到后缀表达式版本：

注意：乘方应该是右结合，所以当s[i]和栈顶都是^时要直接压进去。

#include
#include
#include
#include
#include
using namespace std;
typedef long long ll;
unordered_map<char, int> pr{{'+', 1}, {'-', 1}, {'*', 2}, {'/', 2}, {'^', 3}};
stack<char>num,op;
string s;
bool is_num(int i)
{
    if(s[i]>='0'&&s[i]<='9')
        return true;
    else
    return false;
}
int main()
{
    cin>>s;
 
    for(int i=0;isize();i++)
    {
        if(is_num(i))
        {
            num.push(s[i]);
        }else if(s[i]=='(') op.push(s[i]);
        else if(s[i]==')')
        {
            while(op.top()!='(')
            {
                num.push(op.top());
                op.pop();
            }
            op.pop();
        }else
        {
           while(op.size()&&op.top()!='('&&pr[op.top()]>=pr[s[i]])
            {
                if(s[i]=='^'&&op.top()=='^')break;//乘方是右结和的
                num.push(op.top());
                op.pop();
            }
           op.push(s[i]);
        }
    }
    while(op.size())
    {
        num.push(op.top());
        op.pop();
    }
    while(num.size())
    {
        op.push(num.top());
        num.pop();
    }
    while(op.size())
    {
        cout<top();
        op.pop();
    }
    return 0;
}

得到后缀表达式用于计算版本：

注意：

预处理时在负号前面加0，而不是减号前加0。

一个减号是负号当且仅当减号前的字符不是‘)’和数字。

在实际计算的时候，两个连续的乘方其实先算哪个最后的结果都一样，所以只要求计算结果的话可以当做两个连续优先级相同的普通符号。

#include
#include
#include
#include
#include
#include
using namespace std;
stack<char>ops;
stack<int>nums;
unordered_map<char, int> pr{{'+', 1}, {'-', 1}, {'*', 2}, {'/', 2}, {'^', 3}};
int qmi(int a,int k)
{
    int res=1;
    while(k)
    {
        if(k&1) res=res*a;
        a=a*a;
        k>>=1;
    }
    return res;
}
void cal()
{
    int b=nums.top();nums.pop();
    int a=nums.top();nums.pop();
    char c=ops.top();ops.pop();
    int x;
    if(c=='+') x=a+b;
    else if(c=='-') x=a-b;
    else if(c=='*') x=a*b;
    else if(c=='/') x=a/b;
    else if(c=='^') x=qmi(a,b);
    nums.push(x);
}
int main()
{
    string s;
    cin>>s;
    for(int i=0;isize();i++)
    {
        if(s[i]=='-'&&i==0) s='0'+s;
        else if(s[i]=='-'&&i&&s[i-1]!=')'&&!(s[i-1]>='0'&&s[i-1]<='9'))
        {
            s.insert(i-1,"0");
            i++;
        }
    }
    for(int i=0;isize();i++)
    {
        if(s[i]>='0'&&s[i]<='9')
        {
            int sum=0,j=i;
            while(s[j]>='0'&&s[j]<='9')
                sum=sum*10+s[j++]-'0';
            nums.push(sum);
            i=j-1;
        }else if(s[i]=='(')ops.push(s[i]);
        else if(s[i]==')')
        {
            while(ops.top()!='(') cal();
            ops.pop();
        }else
        {
            while(ops.size()&&ops.top()!='('&&pr[ops.top()]>=pr[s[i]])
                    cal();
            ops.push(s[i]);
        }
    }
    while(ops.size())cal();
    cout<top()<
 
    return 0;
}