牛牛与后缀表达式
牛牛与后缀表达式
https://ac.nowcoder.com/acm/contest/9556/C
后缀表达式转中缀表达式
1、建立一个栈,从左向右扫描后缀表达式,遇到运算数则压入栈;
2、遇到运算符就把栈顶两个元素出栈,执行运算,得到的结果作为新的运算符再压入栈;
3、依次走到表达式结尾;
例如后缀表达式 "12#3#+15#*", 转化为中缀表达式为:
- 数值 12 入栈
- 数值 3 入栈
- 遇到运算符 '+' ,将 12 和 3 出栈,执行加法操作得到 15, 再把 15 入栈
- 数值 15 入栈
- 遇到运算符 '*' ,将 15 和 15 出栈,执行乘法操作得到 225, 再把 225 入栈。
最后栈内的元素 225 就是最后的答案。
这题直接开个栈模拟一下就行,注意要开 long long.
读数字的话,可以用类似于快读的方法来读取。
Code
long long solve(string str) { int n = str.length(); long long sta[1000010]; int i = 0, top = 0; long long s = 0; while(1) { if(i >= n) break; char ch = str[i]; if(ch == '#')//读数字 { sta[++top] = s; s = 0; } else if(ch == '+')//加法操作 { long long a = sta[top--]; long long b = sta[top--]; sta[++top] = a+b; } else if(ch == '-')//减法操作 { long long a = sta[top--]; long long b = sta[top--]; sta[++top] = b-a; } else if(ch == '*')//乘法操作 { long long a = sta[top--]; long long b = sta[top--]; sta[++top] = a * b; } else { s = s * 10 + str[i] - '0'; } i++; } return sta[top]; }