对了有同学说C用realloc好像通不过，那不用realloc该怎么改呢？
谢谢！
题目：中缀表达式与后缀表达式
Description
将一个后缀表达式转换为一个中缀表达式。
Input Description
一个合法的后缀表达式。它由一串连续的操作数与运算符的序列构成。操作数用英文小写字母表示,且运算符只有五种,每个运算符只有一种符号表示。相邻的操作数与运算符之间均没有任何分隔符。
输入中会出现的运算符
运算符 符号 优先级 备注
阶乘 ! 高 一元运算符
乘号 * 中
除号 / 中
加号 + 低
减号 - 低
Output Description
一个中缀表达式,它由一串连续的操作数与操作符的序列构成,它与输入的后缀表达式表达同一个算术表达式。由于中缀表达式会遇到运算符的优先级问题,你需要适当地插入左括号和右括号来调整运算的优先级。输出中允许出现的运算符有七种,每个运算符只有一种符号表示。除了操作数和运算符不允许输出任何空格、换行等分隔符。
输出中允许出现的运算符
运算符 符号 优先级 备注
左括号 ( 最高
右括号 ) 最高 与左括号搭配使用
阶乘 ! 高 一元运算符
乘号 * 中
除号 / 中
加号 + 低
减号 - 低
为了减少括号的数量以及保证输出唯一性，我们要求你尽可能地避免括号的使用，除非这样做将改变表达式中某些运算的发生次序。特别要注意，左右操作数的顺序是不可改变的，我们认为 a + b 和 b + a 是不同的表达式。对于满足 结合律的运算，运算发生次序不变的情况下应该省略括号，否则不能省略括号：我们认为 (a + b) + c 与 a + b + c 是同样的表达式，而 a + (b + c) 与 a + b + c是不同的。例如： (a + b) + (c + d) 中，如果删除第一对括号，运算结果和运算次序都没有变化；如果删除第二对括号，运算结果没有变化，但是 a + b 会首先与 c 相加，导致运算次序变化。所以这种情况下应该输出 a + b + (c + d)。
Input Sample
ab+cde*f*+fd+qp-!*-+
Output Sample
a+b+(c+d*e*f-(f+d)*(q-p)!)
Hint
你可以将生成的中缀表达式转换回后缀表达式,以验证中缀表达式的正确性。 请你自行想办法验证它是否是括号最少而不影响运算次序的结果。
我的两个版本：
c++版本：
#include<iostream>
#include<string>
//#define STACK_SIZE 7000//栈的大小，可以容纳1000个表达式 使用宏定义全局变量，方便修改
//#define StringNode_SIZE 7000//StringNode 类对象中的字符串数组大小
using namespace std;
// 定义栈的数据结构。
int JudgePriority(char c);//向前引用声明 判断运算符c的优先级
int Length;//全局变量
class StringNode {//Stringnode节点，存储每一个表达式及其优先级
private:
string STring;
int priority;//优先级
public:
StringNode() {
// STring = "\0";
priority = 10;//默认初始状态
}
StringNode(char Char1) {//单个字符建立对象，只有字母是需要这种情况
STring = Char1;
priority = 4;//设定字母优先级为4，是最高,括号4与单个字母等价，阶乘3
}
StringNode(string ExpressionString, int Priority1) {//表达式字符串建立对象
// STring.at(0) = '\0';//防止栈访问出错
STring = ExpressionString;
priority = Priority1;
}
friend StringNode Compose(StringNode &SN1, char Operator, StringNode &SN2) {//由两个表达式和一个运算符组成一个新的表达式 加括号也是在这一步
AutoAddBrackets(SN1, Operator, SN2);//如果需要的话自动给SN1，2加括号
return StringNode(SN1.STring + Operator + SN2.STring, JudgePriority(Operator));
}
friend StringNode Compose(StringNode &SN1, char Operator) {//由一个表达式和一个单目运算符（！）组成一个新的表达式 加括号也是在这一步
AutoAddBrackets(SN1, Operator);//如果需要的话自动给SN1加括号
SN1.STring += Operator;
return StringNode(SN1.STring, 3);//这个运算符的优先级就给了合成的表达式（必然是阶乘的3）
}
friend void AutoAddBrackets(StringNode &SN1, char Operator, StringNode &SN2) {//使用引用！为了修改实参
if (SN1.priority >= JudgePriority(Operator) && JudgePriority(Operator) >= SN2.priority) {
SN2.AddBrackets();return;
}
else if (SN1.priority == 1 && (Operator=='*'|| Operator == '/') && SN2.priority >= 3) {
SN1.AddBrackets();return;
}
else if (SN1.priority == 1 && (Operator == '*' || Operator == '/') && SN2.priority <= 2) {
SN1.AddBrackets();SN2.AddBrackets();return;
}
else//两边都不加括号情况，最多
return;
}
friend void AutoAddBrackets(StringNode &SN1, char Operator) {
if (SN1.priority<3 ) {//如果是！
SN1.AddBrackets();
}
}
void AddBrackets() {
STring = STring.insert(0,1,'(') + ")";
priority = 4;//加括号以后，优先级变得和数字一样高
}
void PrintString() {//输出本对象中的STring字符串
cout << STring;
}
};
class Stack {
private:
StringNode *Buffer; //保存栈中的数据，指向栈首
int top; //栈的深度
public:
Stack(int Len) {
Buffer = new StringNode[Len];//这个数组只能用Buffer来指示，不能起一个数组名
top = 0;//初始没有元素，top指代第零个
}
void push(StringNode val) { //压栈操作
Buffer[top++] = val;
}
StringNode pop() { //出栈操作
top--;//由于top总是指向下一个还没有值的位置，因此先要把top后退一位
return Buffer[top];
}
void PrintStack() {//最终的输出
Buffer[0].PrintString();
}
};
bool IsCharacter(char c) {//判字母函数
return c >= 'a'&&c <= 'z';
}
bool IsBiOperator(char c) {//判二元运算符
return c == '+' || c == '*' || c == '/' || c == '-';
}
bool IsSingleOperator(char c) {//判一元运算符（！）
return c == '!';
}
int JudgePriority(char c) {//返回操作符号的优先级
if (c == '+' || c == '-')//if判断必须加括号，return可以不用
return 1;
else if (c == '*' || c == '/')
return 2;
else if (c == '!')
return 3;
else
return 10;//出错情况
}
int main()
{
int c = 0;//用于一个一个读取字符
string Str;
cin >> Str;
Length = Str.size();
Stack StackObject(Length);//建立栈对象
while (c < Str.size()) {//通过c读取一个字符
if (IsCharacter(Str.at(c))) {//如果是字母就入栈
StackObject.push(StringNode(Str.at(c)));
}
else if (IsBiOperator(Str.at(c))) {//如果是二目运算符，出栈两个节点后合成再入栈
StringNode TempSN1 = StackObject.pop();
StringNode TempSN2 = StackObject.pop();//注意出栈后的顺序
StackObject.push(Compose(TempSN2, Str.at(c), TempSN1));//2在前面
}
else if (IsSingleOperator(Str.at(c))) {//如果是一目运算符
StringNode TempSN = StackObject.pop();
StackObject.push(Compose(TempSN, Str.at(c)));
}
c++;
}
StackObject.PrintStack();
}
c版本：
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
struct Node {
char NodeChar;
struct Node *next;//每个节点存储一个字符和指向下一个节点的指针
};
struct HeadNode {//头结点记录表达式信息，有指向后续节点的头指针，后续节点数（字符数），以及表达式的优先级。一个头结点后面跟着一串结点链表代表一个表达式
struct Node *head;
int CharNum;
int priority;
};
void Bracket(struct HeadNode *H) {//给头结点指针H指向的头结点表示的表达式加括号
int i;
struct Node *p = (*H).head;
struct Node *q;
for (i = 0;i < ((*H).CharNum) - 1;i++) {//一直把p移动到尾节点的前一个节点（指向尾节点）
p = p->next;
}
p->next = malloc(sizeof(struct Node));//尾指针新开辟一个节点
p = p->next;//p指向这个新的尾节点
(*p).NodeChar = ')';//尾节点上的字符时右括号
p->next = NULL;//尾节点的尾指针为NULL
q = malloc(sizeof(struct Node));//用一个指向节点的指针q申请一个节点
q->next = (*H).head;
q->NodeChar = '(';
H->head = q;
(H->CharNum) += 2;
H->priority = 4;
}
void AddChar(struct HeadNode *H, char c) {
int i;
struct Node *p = (*H).head;
for (i = 0;i < (*H).CharNum - 1;i++) {//只移动到上一项，这样才能修改指针的值
p = p->next;
}
p->next = malloc(sizeof(struct Node));//这样才能真正改动Stack数组中的值
p = p->next;
p->NodeChar = c;
p->next = NULL;
(H->CharNum)++;
if (c == '+' || c == '-') {
H->priority = 1;
}
else if (c == '*' || c == '/') {
H->priority = 2;
}
else if (c == '!') {
H->priority = 3;
}
}
void Merge(struct HeadNode *H1, struct HeadNode *H2) {
int i;
struct Node *p = (*H1).head;
struct Node *q;
for (i = 0;i < (*H1).CharNum - 1;i++) {
p = p->next;
}
p->next = H2->head;
(H1->CharNum) = (H1->CharNum) + (H2->CharNum);
free(H2);
}
void DeleteHeadNode(struct HeadNode *H) {
struct Node *j = (*H).head;
struct Node *q = (*H).head;
int i = (*H).CharNum;
for (;i > 0;i--) {
q = q->next;
free(j);
j = q;
}
free(H);
}
main() {
int i;
char c;
struct HeadNode ** Stack = NULL;
int top = 0;
while (c = getchar()) {//getchar连回车都读入
if (c == '\n')
break;
if (c >= 'a'&&c <= 'z') {
struct HeadNode *H = malloc(sizeof(struct HeadNode));
if (H) {
H[0].priority = 4;
H[0].head = malloc(sizeof(struct Node));
H[0].CharNum = 1;
H[0].head->NodeChar = c;
H[0].head->next = NULL;
if (!Stack) {
Stack = malloc(sizeof(struct HeadNode *));
}
else {
Stack = realloc(Stack, sizeof(struct HeadNode *)*(top+1));
}
Stack[top] = H;
top++;
}
else {
exit(0);
}
}
else if (c == '!') {
int i;
struct Node *p = (*(Stack[top - 1])).head;
if ((*(Stack[top - 1])).priority < 3) {
Bracket(Stack[top - 1]);
}
AddChar(Stack[top - 1], '!');
}
else {
int cc;
if (c == '+' || c == '-')
cc = 1;
else if (c == '*' || c == '/')
cc = 2;
if ((*(Stack[top - 2])).priority == 1 && (*(Stack[top - 1])).priority <= 2 && cc == 2) {
Bracket(Stack[top - 2]);
Bracket(Stack[top - 1]);
AddChar(Stack[top - 2], c);
Merge(Stack[top - 2], Stack[top - 1]);
top--;
}
else if ((*(Stack[top - 2])).priority >= cc&&cc >= (*(Stack[top - 1])).priority) {
Bracket(Stack[top - 1]);
AddChar(Stack[top - 2], c);
Merge(Stack[top - 2], Stack[top - 1]);
top--;
}
else if ((*(Stack[top - 2])).priority < cc&&cc < (*(Stack[top - 1])).priority) {
Bracket(Stack[top - 2]);
AddChar(Stack[top - 2], c);
Merge(Stack[top - 2], Stack[top - 1]);
top--;
}
else {
AddChar(Stack[top - 2], c);
Merge(Stack[top - 2], Stack[top - 1]);
top--;
}
}
}
struct Node *pp = (*(Stack[0])).head;
for (i = 0;i < (*(Stack[0])).CharNum;i++, pp = pp->next) {
printf("%c", pp->NodeChar);
}
DeleteHeadNode(Stack[0]);
}
8 个解决方案
#1
1. profile 一下，看看到底慢在哪里。
2. 如果确实是 string 慢，再想办法，比如用 string_view 之类的技术。
2. 如果确实是 string 慢，再想办法，比如用 string_view 之类的技术。
#2
不好意思，技术小白，profile和string_view都不会啊
#3
stack overflow! 我猜。
#4
为啥溢出？
#6
这样应该够快, 就是内存多用点 ...
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <assert.h>
#define MAX_INPUT_SIZE (1 << 12)
#define MAX_STACK_SIZE (MAX_INPUT_SIZE / 2 + 64)
enum {
kET_Atom,
kET_High,
kET_Mid,
kET_Low
};
typedef struct
{
int kExprType, kExprLen;
char kExprValue[2*MAX_INPUT_SIZE - 2*sizeof(int)];
} ST_expr;
int solve(const char* input_expr, ST_expr* stack)
{
int top = 0, c;
ST_expr *curr, *left, *right;
while(0 != (c = *input_expr++))
{
assert(top >= 0);
if(top >= MAX_STACK_SIZE - 1)
return -2;
switch(c)
{
case ' ':
case '\t':
case '\r':
case '\n':
case '\f':
/* ignore space */
break;
case '+':
case '-':
if(top < 2) return -1;
left = curr = &stack[top - 2];
right = &stack[top - 1];
--top;
curr->kExprValue[curr->kExprLen++] = c;
if(right->kExprType == kET_Low)
{
curr->kExprValue[curr->kExprLen++] = '(';
memcpy(curr->kExprValue + curr->kExprLen, right->kExprValue, right->kExprLen);
curr->kExprLen += right->kExprLen;
curr->kExprValue[curr->kExprLen++] = ')';
}
else
{
memcpy(curr->kExprValue + curr->kExprLen, right->kExprValue, right->kExprLen);
curr->kExprLen += right->kExprLen;
}
curr->kExprValue[curr->kExprLen] = 0;
curr->kExprType = kET_Low;
break;
case '*':
case '/':
if(top < 2) return -1;
left = curr = &stack[top - 2];
right = &stack[top - 1];
--top;
if(curr->kExprType == kET_Low)
{
memmove(curr->kExprValue + 1, curr->kExprValue, curr->kExprLen);
curr->kExprValue[0] = '(';
curr->kExprValue[1 + curr->kExprLen] = ')';
curr->kExprLen += 2;
}
curr->kExprValue[curr->kExprLen++] = c;
if(right->kExprType >= kET_Mid)
{
curr->kExprValue[curr->kExprLen++] = '(';
memcpy(curr->kExprValue + curr->kExprLen, right->kExprValue, right->kExprLen);
curr->kExprLen += right->kExprLen;
curr->kExprValue[curr->kExprLen++] = ')';
}
else
{
memcpy(curr->kExprValue + curr->kExprLen, right->kExprValue, right->kExprLen);
curr->kExprLen += right->kExprLen;
}
curr->kExprValue[curr->kExprLen] = 0;
curr->kExprType = kET_Mid;
break;
case '!':
if(top < 1) return -1;
curr = &stack[top - 1];
if(curr->kExprType >= kET_Mid)
{
memmove(curr->kExprValue + 1, curr->kExprValue, curr->kExprLen);
curr->kExprValue[0] = '(';
curr->kExprValue[1 + curr->kExprLen] = ')';
curr->kExprValue[2 + curr->kExprLen] = '!';
curr->kExprLen += 3;
}
else
{
curr->kExprValue[curr->kExprLen++] = '!';
}
curr->kExprValue[curr->kExprLen] = 0;
curr->kExprType = kET_High;
break;
default:
stack[top].kExprLen = 1;
stack[top].kExprType = kET_Atom;
stack[top].kExprValue[0] = c;
stack[top].kExprValue[1] = 0;
++top;
break;
}
}
return top;
}
int main()
{
int err = 0, r;
char* input_expr;
ST_expr* stack;
input_expr = (char*)calloc(1, MAX_INPUT_SIZE + 16);
stack = (ST_expr*)malloc(sizeof(ST_expr)*MAX_STACK_SIZE);
while(NULL != fgets(input_expr, MAX_INPUT_SIZE, stdin))
{
r = solve(input_expr, stack);
switch(r)
{
case 0:
/* empty line */
break;
case 1:
printf("%s\n", stack[0].kExprValue);
break;
default:
fprintf(stderr, "%d, ERROR(%d): %s\n", ++err, r, input_expr);
}
}
free(input_expr);
free(stack);
return err;
}
#7
嘻嘻，您的方法通过了前四个，挂了后六个测试，可能是哪里没太符合题目要求的细节吧，还是感谢啦！我用同学的方法通过了
#8
楼主最后是怎么改的？能否贴一下代码
#1
1. profile 一下，看看到底慢在哪里。
2. 如果确实是 string 慢，再想办法，比如用 string_view 之类的技术。
2. 如果确实是 string 慢，再想办法，比如用 string_view 之类的技术。
#2
不好意思，技术小白，profile和string_view都不会啊
#3
stack overflow! 我猜。
#4
为啥溢出？
#5
#6
这样应该够快, 就是内存多用点 ...
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <assert.h>
#define MAX_INPUT_SIZE (1 << 12)
#define MAX_STACK_SIZE (MAX_INPUT_SIZE / 2 + 64)
enum {
kET_Atom,
kET_High,
kET_Mid,
kET_Low
};
typedef struct
{
int kExprType, kExprLen;
char kExprValue[2*MAX_INPUT_SIZE - 2*sizeof(int)];
} ST_expr;
int solve(const char* input_expr, ST_expr* stack)
{
int top = 0, c;
ST_expr *curr, *left, *right;
while(0 != (c = *input_expr++))
{
assert(top >= 0);
if(top >= MAX_STACK_SIZE - 1)
return -2;
switch(c)
{
case ' ':
case '\t':
case '\r':
case '\n':
case '\f':
/* ignore space */
break;
case '+':
case '-':
if(top < 2) return -1;
left = curr = &stack[top - 2];
right = &stack[top - 1];
--top;
curr->kExprValue[curr->kExprLen++] = c;
if(right->kExprType == kET_Low)
{
curr->kExprValue[curr->kExprLen++] = '(';
memcpy(curr->kExprValue + curr->kExprLen, right->kExprValue, right->kExprLen);
curr->kExprLen += right->kExprLen;
curr->kExprValue[curr->kExprLen++] = ')';
}
else
{
memcpy(curr->kExprValue + curr->kExprLen, right->kExprValue, right->kExprLen);
curr->kExprLen += right->kExprLen;
}
curr->kExprValue[curr->kExprLen] = 0;
curr->kExprType = kET_Low;
break;
case '*':
case '/':
if(top < 2) return -1;
left = curr = &stack[top - 2];
right = &stack[top - 1];
--top;
if(curr->kExprType == kET_Low)
{
memmove(curr->kExprValue + 1, curr->kExprValue, curr->kExprLen);
curr->kExprValue[0] = '(';
curr->kExprValue[1 + curr->kExprLen] = ')';
curr->kExprLen += 2;
}
curr->kExprValue[curr->kExprLen++] = c;
if(right->kExprType >= kET_Mid)
{
curr->kExprValue[curr->kExprLen++] = '(';
memcpy(curr->kExprValue + curr->kExprLen, right->kExprValue, right->kExprLen);
curr->kExprLen += right->kExprLen;
curr->kExprValue[curr->kExprLen++] = ')';
}
else
{
memcpy(curr->kExprValue + curr->kExprLen, right->kExprValue, right->kExprLen);
curr->kExprLen += right->kExprLen;
}
curr->kExprValue[curr->kExprLen] = 0;
curr->kExprType = kET_Mid;
break;
case '!':
if(top < 1) return -1;
curr = &stack[top - 1];
if(curr->kExprType >= kET_Mid)
{
memmove(curr->kExprValue + 1, curr->kExprValue, curr->kExprLen);
curr->kExprValue[0] = '(';
curr->kExprValue[1 + curr->kExprLen] = ')';
curr->kExprValue[2 + curr->kExprLen] = '!';
curr->kExprLen += 3;
}
else
{
curr->kExprValue[curr->kExprLen++] = '!';
}
curr->kExprValue[curr->kExprLen] = 0;
curr->kExprType = kET_High;
break;
default:
stack[top].kExprLen = 1;
stack[top].kExprType = kET_Atom;
stack[top].kExprValue[0] = c;
stack[top].kExprValue[1] = 0;
++top;
break;
}
}
return top;
}
int main()
{
int err = 0, r;
char* input_expr;
ST_expr* stack;
input_expr = (char*)calloc(1, MAX_INPUT_SIZE + 16);
stack = (ST_expr*)malloc(sizeof(ST_expr)*MAX_STACK_SIZE);
while(NULL != fgets(input_expr, MAX_INPUT_SIZE, stdin))
{
r = solve(input_expr, stack);
switch(r)
{
case 0:
/* empty line */
break;
case 1:
printf("%s\n", stack[0].kExprValue);
break;
default:
fprintf(stderr, "%d, ERROR(%d): %s\n", ++err, r, input_expr);
}
}
free(input_expr);
free(stack);
return err;
}
#7
嘻嘻，您的方法通过了前四个，挂了后六个测试，可能是哪里没太符合题目要求的细节吧，还是感谢啦！我用同学的方法通过了
#8
楼主最后是怎么改的？能否贴一下代码