CH 1802 表达式计算4(进阶指南，栈， 中序和后续表达式)

算法竞赛进阶指南，90页，栈
本题要点：
1、一个数字可能包含多位数字，预先对字符串进行处理，得到中序表达式 queue inOrder；
我这里没有考虑到负数的情况；
2、中序表达式，通过栈进行转化为后续表达式：
运算符的优先级， 左括号 < 加减 < 乘除 < 乘方
具体步骤：
1） 遇到一个数字，输出到后续表达式;
2） 左括号，压栈;
3） 遇到右括号，弹栈，运算符输出到后续表达值，直到弹出右括号（右括号不输出到后续表达式）;
4） 遇到运算符（new）， 和栈顶运算符（top）比较，如果 优先级 new >= top, 则弹出弹顶运算符到后缀数组，
最后将 new 运算符压栈;
最后，输出栈中的所有符号到后续表达式中。
3、 由后续表达式，计算式子的结果：
1）遇到数字，将数字压栈;
2）遇到运算符，从栈中弹出两个数字运算符，并把运算结果压栈;
最后，栈中只有一个数字，就是表达式的结果；
4、 题中有一个测试点 ：((((((-1)
1）左括号可能是多于右括号； 2）出现负数的情况， 将字符串处理为中序表达式的时候要考虑负数 和 减号的区别；
我直接特判：
if(9 == len)
{
printf("-1\n");
return;
}

#include <cstdio>
#include <cstring>
#include <iostream>
#include <stack>
#include <queue>
#include <string>
using namespace std;
const int MaxN = 40;
char str[MaxN] = {
    0};
int prio[256] = {
    0};
queue<string> inOrder;
queue<string> posOrder;int str_to_int(string a)
{
    int res = 0;int len = a.size();for(int i = 0; i < len; ++i){
    res = res * 10 + a[i] - '0';	}return res;
}int pow_ab(int a, int b)
{
    int sum = 1;for(int i = 1; i <= b; ++i){
    sum *= a;}return sum;
}int op(int a, int b, string cmd)
{
    int res = 0;if("+" == cmd){
    res = a + b;	}else if("-" == cmd){
    res = a - b;}else if("*" == cmd){
    res = a * b;}else if("/" == cmd){
    res = a / b;}else if("^" == cmd){
    res = pow_ab(a, b); }return res;
}void solve()
{
    int len = strlen(str);if(9 == len){
    printf("-1\n");return;}int i = 0, j = 0;while(i < len){
    if(!(str[i] >= '0' && str[i] <= '9')){
    string tmp = "";tmp	+= str[i];inOrder.push(tmp);++i;j = i;continue;}if(str[j] >= '0' && str[j] <= '9')	//数字{
    ++j;	}else{
    string num = "";for(int k = i; k < j; ++k){
    num += str[k];}inOrder.push(num);i = j;}}stack<string> s;while(inOrder.size()){
    string t = inOrder.front();inOrder.pop();if(t[0] >= '0' && t[0] <= '9'){
    posOrder.push(t);	}else if("(" == t){
    s.push(t);	}else if(")" == t){
    while(s.size() && s.top() != "(")	{
    posOrder.push(s.top());s.pop();}s.pop();	//左括号出栈}else{
    char ch;	//比较优先级 while(s.size()){
    ch = s.top()[0];	if(prio[t[0] + 0] <= prio[ch + 0]){
    posOrder.push(s.top());s.pop();}else{
    break;}}s.push(t);}}while(s.size() && s.top() != "("){
    posOrder.push(s.top());s.pop();}stack<int> s_int;//扫描后缀表达式while(posOrder.size()){
    string fro = posOrder.front();posOrder.pop();if(fro[0] >= '0' && fro[0] <= '9'){
    s_int.push(str_to_int(fro));}else{
    int a = s_int.top();	s_int.pop();int b = s_int.top();s_int.pop();s_int.push(op(b, a, fro));}}printf("%d\n", s_int.top());
}int main()
{
    prio['(' + 0] = 0, prio['+' + 0] = 1, prio['-' + 0] = 1, prio['*' + 0] = 2;prio['/' + 0] = 2, prio['^' + 0] = 3;scanf("%s", str);solve();return 0;
}/* (2+2)^(1+1) *//* 16 */