题解 P1175 【表达式的转换】

· · 题解

蒟蒻没想到随便交了下就过了orz，使用的方法应该是最单纯的

分为两步：1.转后缀表达式存到last数组里

2.一边计算一边输出过程，我想到了一个比较好的方法

1：转后缀表达式，过程如下（数组均指last数组） ①遇到一个数直接存进数组
②遇到左括号，把他放进栈里
③遇到右括号，不断取出栈顶存进数组里
④遇到运算符，只要栈顶的运算符优先级大于等于当前读入的符号，就不断取出栈顶符号存入数组，最后把读入的符号进栈。优先级：乘方 > 乘除 > 加减 > 左括号。（右括号不会进栈）优先级定义详情看代码。
⑤依次把栈里的元素转存到数组里 2:计算过程并输出，使用一个数组模拟的栈，方便我们遍历，Top变量代表栈顶，start变量代表在last数组里的一个光标，因为我们采用的输出方式为：将栈中Top之前的变量输出，再将lst数组中start光标之后的所有元素输出就可以将一个过程完整的表达式，不理解的话可以看一下代码的具体操作体会一下
①遇到一个数，存进栈里，并将start后移一位 ②遇到运算符，从栈顶连续取出两个元素进行运算，答案继续压栈（此时Top指针之前加上str指针之后的就是一个完整的式子） 代码 

#include <cstdio>
#include <cstring>
#include <iostream>
#include <stack>
#define ll long long
using namespace std;

int tot;
char a[1100],lst[1100];
int lev[300];
stack<char> s;
stack<int> Pro;
int len;

void E_change();
void cal();
void add(char);
int cf(int,int);

int main()
{
    lev['^'] = 7,lev['*'] = 6,lev['/'] = 6,lev['+'] = 5,lev['-'] = 5,lev['('] = 4;//优先级定义，简单粗暴
    scanf("%s",a);
    len = strlen(a);
    E_change();
    int l = strlen(lst);
    for(int i = 0; i < l; ++i) printf("%c ",lst[i]);    //输出后缀表达式
    printf("\n");
    cal();      //计算
    return 0;
}

void E_change()             //转换后缀表达式
{
    char c;
    for(int i = 0; i <= len - 1; ++i){
        c = a[i];
        if(c >= '0' && c <= '9'){add(c);continue;}
        if(c == '(') {s.push(c);continue;}
        if(c == ')') {
            while(s.top() != '('){
                add(s.top());
                s.pop();
            }
            s.pop();
            continue;
        }
        if( (c == '+' || c == '-' || c == '*' || c == '/' || c == '^' )){
            if(s.empty()) {s.push(c);continue;}
            while(!s.empty()){
                char ch = s.top();
                if(lev[ch] < lev[c]) break;
                if(lev[ch] >= lev[c]){
                add(ch);
                s.pop();
                }
            }
            s.push(c);
        }
    }
    while(!s.empty()){
        add(s.top());
        s.pop();
    }
}

void cal()
{
    int Pro[10001];
    int Top = 0,str = 0;
    int l = strlen(lst);
    for(int i = 0 ; i < l; ++i){
        char c = lst[i];
        if(c >= '0' && c <= '9') {Pro[Top] = c - 48;Top++;str++;}
        else{
            int a = Pro[--Top];
            int b = Pro[--Top];
            str++;              
            int ans;
            if(c == '+') ans = a + b;
            else if(c == '-') ans = b - a;
            else if(c == '*') ans = a * b;
            else if(c == '/') ans = b / a;
            else if(c == '^') ans = cf(b,a);
            Pro[Top] = ans;
            for(int j = 0; j <= Top; ++j) printf("%d ",Pro[j]);//栈中有一半式子
            for(int j = str; j < l; ++j) printf("%c ",lst[j]);//str后面的都是未进栈的数
                //两部分相拼就是完整的一个表达式
            Top++;
            printf("\n");
        }
    }
}

int cf(int x,int y)
{               //乘方运算
    ll sum = 1;
    for(int i = 1; i <= y; i++) sum = sum * x;
    return sum;
}

void add(char x)
{
    lst[tot++] = x;
//  lst[++tot] = ' ';
}