include [HTML_REMOVED]

include [HTML_REMOVED]

include [HTML_REMOVED]

using namespace std;
// 栈模拟表达式求值
int prior(char e)
{
if (e == ‘+’ || e == ‘-‘)
{
return 1;
}
if (e == ‘‘ || e == ‘/’)
{
return 2;
}
if (e == ‘^’)
{
return 3;
}
return 0;
}
int calculate(int num1, int num2, char e)
{
if (e == ‘+’)
{
return num1 + num2;
}
else if (e == ‘-‘)
{
return num1 - num2;
}
else if (e == ‘’)
{
return num1 * num2;
}
else if (e == ‘/’)
{
if (num2 == 0)
{
return 0;
}
else
{
return num1 / num2;
}
}
else if (e == ‘^’)
{
return pow(num1, num2);
}
}
int pop1(int stack, int &top)
{
if (top != -1)
{
int number;
number = stack[top];
stack[top] = NULL;
top–;
return number;
}
}
char pop2(char stack, int &top)
{
if (top != -1)
{
char e;
e = stack[top];
stack[top] = NULL;
top–;
return e;
}
}
void push1(int stack, int &top, int value)
{
top;
stack[top] = value;
}
void push2(char *stack, int &top, char e)
{
top;
stack[top] = e;
}
int main()
{
int ans;
// 最终答案
int stack_number[10000];
int stack_number_top = -1;
// 放数字的栈
char stack_operater[10000];
int stack_operater_top = -1;
// 放运算符的栈
// 运算符优先级:^高于/高于+-
// 括号优先级最高
string a;
cin >> a;
int a_length = a.length();
// 输入表达式
bool neg = false;
// 判断输入数字是否为负号而非减号 是负数是true 不是时false
bool neg_2 = false;
// 判断括号前面是否是负号 是负号是true 不是则为false
for (int i = 0; i < a_length; i)
{
if (a[i] - ‘0’ >= 0 && a[i] - ‘0’ <= 9)
// 处理输入的是数字
{
int j = 1;
int num = 0;
while (a[i + j] - ‘0’ >= 0 && a[i + j] - ‘0’ <= 9)
{
j;
}
int t = 1;
for (int v = i + j - 1; v >= i; v–)
{
num += (a[v] - ‘0’) * t;
t = t * 10;
}
if (neg == true)
{
num = num * (-1);
}
push1(stack_number, stack_number_top, num);
i += (j - 1);
num = 0;
neg = false;
}
else if (a[i] - ‘(‘ == 0)
{
stack_operater_top++;
stack_operater[stack_operater_top] = ‘(‘;
}
else if (a[i] == ‘)’)
{
while (stack_operater_top != -1 && stack_operater[stack_operater_top] != ‘(‘)
{
int num2 = pop1(stack_number, stack_number_top);
int num1 = pop1(stack_number, stack_number_top);
char e = pop2(stack_operater, stack_operater_top);
int value = calculate(num1, num2, e);
if (neg_2 == true)
{
value = value * (-1);
}
push1(stack_number, stack_number_top, value);
neg_2 = false;
}
if (stack_operater_top != -1)
{
pop2(stack_operater, stack_operater_top);
}
}
else if (a[i] - ‘+’ == 0 || a[i] - ‘-‘ == 0 || a[i] - ‘‘ == 0 || a[i] - ‘/’ == 0 || a[i] - ‘^’ == 0)
{
// 对于一个运算符可以有以下处理方式
//-作为负号 设置neg或者neg_2标识位 不要入栈 结束这个a[i]
// stack_operater_top==-1 第一个输入的运算符 直接入栈
// 普通的运算符 和栈里现有top处运算符比较 top处优先级高就先计算top处的表达式(确保至少有两个操作数)
int flag = 0;
// 确保只进栈一次
if (a[i] == ‘-‘ && (i == 0 || (a[i - 1] - ‘+’ == 0 || a[i - 1] - ‘-‘ == 0 || a[i - 1] - ‘‘ == 0 || a[i - 1] - ‘/’ == 0) || (!(a[i - 1] - ‘0’ >= 0 && a[i - 1] - ‘0’ <= 9) && (!a[i - 1] == ‘)’)) || (a[i - 1] == ‘(‘)))
// 负号的情况 (1) 第一个字符 (2) 不能前一个字符是数字 (3)上一个字符是( (4) 不能前一个字符是) (5) 前一个字符是+-*/
{
if (a[i + 1] == ‘(‘)
// 括号前面是负号的情况
{
neg_2 = true;
}
else
{
neg = true;
// 数字前面是负号的情况
}
flag = 1;
// 负号不用进栈
continue;
}
if (stack_operater_top == -1 && stack_number_top != -1)
{
push2(stack_operater, stack_operater_top, a[i]);
flag = 1;
// 输入的是第一个运算符 直接进栈
}
else if (stack_operater_top != -1 && stack_number_top >= 0 && prior(stack_operater[stack_operater_top]) >= prior(a[i]))
{
int num2 = pop1(stack_number, stack_number_top);
int num1 = pop1(stack_number, stack_number_top);
push1(stack_number, stack_number_top, calculate(num1, num2, pop2(stack_operater, stack_operater_top)));
// 运算符栈中有运算符而且栈内运算符优先级大于此时读入的运算符 先计算栈内的表达式
flag = 1;
push2(stack_operater, stack_operater_top, a[i]);
}
if (flag == 0)
{
push2(stack_operater, stack_operater_top, a[i]);
}
}
else
{
cout << “wrong input” << endl;
break;
}
// 读入表达式 按照操作符和数字分开放置在两个栈中
}
while (stack_operater_top != -1)
{
if (stack_operater[stack_operater_top] == ‘(‘ || stack_operater[stack_operater_top] == ‘)’)
{
char rubbish = pop2(stack_operater, stack_operater_top);
}
else
{
int num2 = pop1(stack_number, stack_number_top);
int num1 = pop1(stack_number, stack_number_top);
char e = pop2(stack_operater, stack_operater_top);
push1(stack_number, stack_number_top, calculate(num1, num2, e));
}
}
// 输出最终结果
if (stack_number_top == 0)
{
ans = stack_number[stack_number_top];
cout << ans << endl;
}
return 0;
}

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla