C++ 从表达式中删除无效的括号

1. 前言

在C++编程过程中,遇到一个表达式中有大量的无用括号时,我们可以通过一定的代码操作来将这些无用括号删除,从而使代码更加简洁高效。本文将介绍如何在C++中删除无效的括号,希望对大家的编程工作有所帮助。

2. 什么是无效括号

在C++中,括号是用来改变运算符的优先级和确定运算顺序的。然而,在一些情况下,我们往往会在表达式中加入大量的无用括号,这些括号不会影响表达式的含义,但会使代码难以阅读,运行速度变慢。

下面是一个例子,其中有很多无用括号:

int a = (((((1+2)*3)/4)-5)%6)+7;

这个表达式中的很多括号都没有实际意义,可以简化为:

int a = (1 + 2) * 3 / 4 - 5 % 6 + 7;

这个表达式与原表达式的含义是一致的,但从可读性和运行效率上都更好。

3. 实现过程

3.1 删除无效的括号

在C++中,我们可以通过逆波兰表达式来删除无效的括号。逆波兰表达式是一种不需要括号的表达式形式,它通过改变操作数和操作符的位置,使得表达式的含义不变,但括号变得多余。

在逆波兰表达式中,操作数在前面,操作符在后面。比如:

原表达式:2+(3*4)

逆波兰表达式:2 3 4 * +

可以看出,逆波兰表达式将操作符放在了后面,省去了括号,可以更加简洁高效地表达原表达式的含义。

因此,我们可以通过将表达式转换成逆波兰表达式的形式来删除无效的括号。具体实现过程如下:

1. 将中缀表达式转换为后缀表达式。

2. 遍历后缀表达式,如果是操作符,则将其弹出操作数栈,并将结果压入操作数栈中;如果是操作数,则直接压入操作数栈中。

3. 最终留在操作数栈中的就是表达式的值。

下面是一个示例代码:

#include

#include

#include

using namespace std;

bool isOperator(char c) {

return (c == '+' || c == '-' || c == '*' || c == '/');

}

bool isLeftBracket(char c) {

return (c == '(' || c == '[' || c == '{');

}

bool isRightBracket(char c) {

return (c == ')' || c == ']' || c == '}');

}

bool isBracket(char c) {

return (isLeftBracket(c) || isRightBracket(c));

}

bool greaterThanOrEqual(char c1, char c2) {

if (c1 == '(') {

return false;

} else if (c1 == '*' || c1 == '/') {

return (c2 == '+' || c2 == '-');

} else {

return true;

}

}

string toPostfix(string infix) {

stack oprStack;

string postfix = "";

for (int i = 0; i < infix.length(); ++i) {

char c = infix[i];

if (isOperator(c)) {

while (!oprStack.empty()

&& isOperator(oprStack.top())

&& greaterThanOrEqual(oprStack.top(), c)) {

postfix += oprStack.top();

oprStack.pop();

}

oprStack.push(c);

} else if (isLeftBracket(c)) {

oprStack.push(c);

} else if (isRightBracket(c)) {

while (!oprStack.empty() && !isLeftBracket(oprStack.top())) {

postfix += oprStack.top();

oprStack.pop();

}

oprStack.pop();

} else {

postfix += c;

}

}

while (!oprStack.empty()) {

postfix += oprStack.top();

oprStack.pop();

}

return postfix;

}

int evaluate(string infix) {

string postfix = toPostfix(infix);

stack oprStack;

for (int i = 0; i < postfix.length(); ++i) {

char c = postfix[i];

if (isOperator(c)) {

int b = oprStack.top();

oprStack.pop();

int a = oprStack.top();

oprStack.pop();

int result = 0;

switch (c) {

case '+':

result = a + b;

break;

case '-':

result = a - b;

break;

case '*':

result = a * b;

break;

case '/':

result = a / b;

break;

}

oprStack.push(result);

} else {

oprStack.push(c - '0');

}

}

return oprStack.top();

}

int main() {

string infix = "(((1+2)*3)/4)-5%6+7";

int result = evaluate(infix);

cout << result << endl;

return 0;

}

3.2 优化逆波兰表达式

上面的实现过程可以较好地删除无效的括号,但是,逆波兰表达式还存在一些问题。具体地说,逆波兰表达式中不同的操作数和操作符可能占据不同长度的空间,这样会导致一些潜在的问题。下面是一个例子:

表达式:2+3*4

逆波兰表达式:234*+

在这个逆波兰表达式中,2和3占据了1个字符的空间,而4却占据了2个字符的空间。因此,当我们计算表达式的值时,需要确定操作数和操作符的边界。这就使得逆波兰表达式的计算稍微麻烦一些。

为了解决这个问题,我们可以在逆波兰表达式中加入特殊字符,比如空格,以表示不同的操作数和操作符在逆波兰表达式中占据相同的空间。这样,我们就可以方便地确定操作数和操作符的边界。下面是修改过后的逆波兰表达式:

表达式:2+3*4

逆波兰表达式:2 3 4 * +

这个逆波兰表达式与之前的逆波兰表达式虽然表示的是同一个表达式,但它的计算过程更加简单明了。

对于含有无效括号的表达式,我们可以通过以下步骤进行优化:

1. 删除无效的括号。

2. 将中缀表达式转换为逆波兰表达式。

3. 在逆波兰表达式中添加特殊字符,优化表达式的空间占用。

4. 利用优化过后的逆波兰表达式计算表达式的值。

4. 总结

在C++编程中,删除无效的括号可以使代码更加简洁高效。本文介绍了通过逆波兰表达式来删除无效的括号的实现过程,同时还介绍了如何优化逆波兰表达式,避免计算时出现边界问题。通过本文的介绍,相信大家对于删除无效的括号有了更深入的理解。

免责声明:本文来自互联网,本站所有信息(包括但不限于文字、视频、音频、数据及图表),不保证该信息的准确性、真实性、完整性、有效性、及时性、原创性等,版权归属于原作者,如无意侵犯媒体或个人知识产权,请来电或致函告之,本站将在第一时间处理。猿码集站发布此文目的在于促进信息交流,此文观点与本站立场无关,不承担任何责任。

后端开发标签