计算器小括号变大括号怎么打
 
Problem statement:
 
 
 问题陈述： 
 
 
Given N number of parenthesis (pair of opening and closing parenthesis), you have to count all the valid combinations of the parenthesis and print the value.
 
 
 给定N个圆括号(一对圆括号)，您必须计算所有有效的圆括号组合并打印该值。 
 
 
Input:
First-line contains T Testcases,
T no. of lines along with an integer number.

E.g.
3
4
3
5

Constrains:
1≤ T ≤10
1≤ N ≤ 20

Output:
Print the number of possible valid combinations 
of the parenthesis.


 
Example
 
 
 例 
 
 
T = 3

Input:
4
output:
14
{
(((()))), ((()())), ((())()), ((()))(), (()(())), (()()())
(()())(), (())(()), (())()(), ()((())),()(()()), ()(())()
()()(()), ()()()()
}

Input:
3
Output:
5
{
((())), (()()), (())(), ()(()), ()()()
}

Input:
5
Output:
37
{
((((())))), (((()()))), (((())())), (((()))()), (((())))()
((()(()))), ((()()())), ((()())()), ((()()))(), ((())(()))
((())()()), ((())())(), ((()))(()), ((()))()(), (()((())))
(()(()())), (()(())()), (()(()))(), (()()(())), (()()()())
(()()())(), (()())(()), (()())()(), (())((())), (())(()())
(())(())(), (())()(()), (())()()(), ()(((()))), ()((()()))
()((())()), ()((()))(), ()(()(())), ()(()()()), ()(()())()
()(())(()), ()(())()(), ()()((())), ()()(()()), ()()(())()
()()()(()), ()()()()()
}


 
Explanation with example:
 
 
 举例说明： 
 
 
To generate a valid combination with the parenthesis is a try and error process, and we will solve this problem with the recursion approach.
 
 
 生成带括号的有效组合是一个尝试和错误的过程，我们将使用递归方法解决此问题。 
 
 
To solve this problem, we will follow these steps,
 
 
 为了解决这个问题，我们将按照以下步骤操作， 
 
 
We have to initialize a count variable to zero, and an open variable is for open parenthesis, and a close variable is for close parenthesis.
 我们必须将一个count变量初始化为零，一个open变量用于开括号，一个close变量用于闭括号。 
Whenever the open is less than the number then we add an open parenthesis.
 只要空位数小于数字，我们就会添加一个圆括号。 
Whenever the open parenthesis is grater the closing parenthesis then we add closing parenthesis to it.
 只要开放括号圆括号括起来，就要在其上加上封闭括号。 
If the value of open parenthesis equals the number then we add one with the count.
 如果开括号的值等于该数字，则我们将其加一。 
 
C++ Implementation:
 
 
 C ++实现： 
 
 
#include <bits/stdc++.h>
using namespace std;

void traverse(int open, int close, int n, int& count, string str, vector<string>& v)
{
    if (close == n) {
        count++;
        return;
    }
    if (open < n) {
        traverse(open + 1, close, n, count, str + "(", v);
    }
    if (close < open) {
        traverse(open, close + 1, n, count, str + ")", v);
    }
    return;
}

void genarate_parenthesis(int num)
{
    string str = "";
    int open_brace = 0, close_brace = 0, count = 0;
    vector<string> v;
    traverse(open_brace, close_brace, num, count, str, v);
    cout << "Valid combinations : " << count << endl;
}

int main()
{
    int t;
 
    cout << "TestCase : ";
    cin >> t;
 
    while (t--) {
        int num;
        cout << "Enter the number: ";
        cin >> num;
        genarate_parenthesis(num);
    }
    
    return 0;
}


 
Output
 
 
 输出量 
 
 
TestCase : 3
Enter the number: 4
Valid combinations : 14
Enter the number: 3
Valid combinations : 5
Enter the number: 5
Valid combinations : 42



 

  
翻译自: https://www.includehelp.com/icp/count-the-combinations-of-the-parenthesis.aspx
 
 
计算器小括号变大括号怎么打

用python编写一个简单计算器
 
计算器开发需求 实现加减乘除及拓号优先级解析 用户输入 # 1 - 2 * ( (60-30 +(-40/5) * (9-2*5/3 + 7 /3*99/4*2998 +10 * 568/14 )) - (-4*3)/ (16-3*2) ) # 等类似算式后，必须自己解析里面的(),+,-,*,/符号和公式,利用递归算法
 
拿到这个题目时，感觉无从下手。老师说利用开学来3天学习的知识是可以做出来的。然后我认真归纳总结前3天学习的基础知识，经过3天3夜的奋战终于给弄出来了。虽然中途也有想过放弃，但是没有耕耘哪来的收获。如果初学的同学想借鉴的话， 建议自己先仔细想想，如果实在无从下手可以参考下我的。特写此文以自勉。程序中可能出现很多冗余或bug，望勿见笑。下面我先说说我的思路。
 
先构造几个函数方法用来进行最初的运算（加减乘除）
在运算函数中，先传入一个字符串，将字符串利用正则表达式，findall函数生成可以取元素的列表形式，利用返回值，
先进行加法和减法运算，加减法能顺利通过验证，结果无误
在算式中增加乘法和除法，用if语句进行判断，如果有乘法和除法，需优先进行计算，通过验证后
在算式中增加括号，增加括号后，需要进行for循环遍历，如果遍历的元素中包含括号，则优先处理计算括号里面的
利用列表临时存储返回值，赋给原来的算式，进行递归，这样算式越来越精简。最终得出结果。
 
简单流程图如下： 
 
 
以下是实现代码：
 
#!/usr/bin/env python
#-*-coding:utf-8 -*-

import re
# 定义函数
def add(x , y): #相加
    return x + y
def subtract(x, y): #相减
    return x - y
def multiply(x, y):  #相乘
    return x * y
def divide(x, y): #相除
    return x / y

temp=[0] #定义一个临时列表，并且赋值0，用来存储结果
temp1=[] #定义一个临时列表，用来临时存储列表
def sum2(ret):  #定义一个函数用来进行数据的处理，运算
    for index,mark in enumerate(ret):  #遍历列表，赋值给mark
        if  str(mark).count("(")==1 and str(mark).startswith("("):  #如果mark中包含“（”并且以其开头
            ret.pop(index)  #将该值（mark），在列表中移除
            mark1=re.findall('^\(\-[0-9.]+|[0-9.]+|[*/+]|[-]',mark)  #将mark元素，再次生成列表
            h = float(re.sub('\(', '', mark1.pop(0)))  #将该表的第一个元素取出，并且将其中所包含的括号替换移除
            mark1.insert(0,h)  #将重新得到的元素，重新插入列表中
            sum2(mark1)  #调用递归算法，计算该列表
            ret.insert(index,temp[-1]) #将临时存储数据的列表的最后一个元素，插入当前循环的索引位置
        elif str(mark).count("(") >= 1:  #如果mark元素中的括号熟练大于等于1
            mark2 = re.findall('\([^()]+\)', mark) #将mark 元素去除最外层括号
            t2=mark2[0]
            mark3 = re.findall('\((.+)\)', mark2[0]) #将mark 元素去除最外层括号
            r1=re.findall('^\(\-[0-9.]+|[0-9.]+|[*/+]|[-]', mark2[0]) #将mark2生成可以计算的列表形式
            h = float(re.sub('\(', '', r1.pop(0)))  #如果r1 包含括号减号则将括号移除
            r1.insert(0, h)
            r2=re.findall('^\(\-[0-9.]+|[0-9.]+|[*/+]|[-]', mark3[0]) #将mark3生成可以计算的列表形式
            mark4=r1 if str(t2).count("(-")==1 else r2  #进行三目运算，判断mark2（t2）是否包含括号，不同的值赋给mark4
            temp1.clear()  #如果临时存储temp1中有数据，则清空
            temp1.extend(ret)  #算式赋值给临时存储temp1
            sum2(mark4)   #调用递归算法，计算该列表
            q4 = mark.replace(str(mark2[0]), str(temp[-1]))  #将结果值替换该运算位置，赋值给q4
            if str(q4).count("(") >= 1:  #如果字符串q4中，包含括号的数量大于等于1
                ret.pop(index)  #将索引位置移除
                ret.insert(index,q4)  #将新得到的字q4
                sum2(ret)  #调用递归算法，计算该列表
            else:  #如果不存在括号
                ret.pop(index)  #将索引位置移除
                rr = re.findall('[0-9.]+|[*+\-/]+|\([^()]+\)+|\(.+\)+', q4)  #采用正则重新生成可以可以计算列表形式
                for index11, wor in enumerate(rr):   #循环打印 rr中的元素
                    if len(wor) == 2 and wor in "+-*/":  #如果元素wor的长度等于2 并且包含于 符号 "+-*/"，就是同时出现两个运算符号，其中有一个减号
                        rr.pop(index11)  #移除该索引的元素
                        rr.insert(index11, wor[0])  #将wor元素的第一个运算符插入原来的位置
                        rrr = rr.pop(index11 + 1)  #将下一个索引元素移除
                        rr.insert(index11 + 1, wor[1] + rrr)  #将wor元素的第二个运算符与当前索引的下一个元素合并
                        sum2(rr)  #调用递归算法，计算该列表
                        q4=temp[-1]  #将结果值赋值给q4，就是更新q4 （这里经过计算后，q4 是一个数字了）

                ret.insert(index,q4)  # 将q4 插入到当前运算式的位置
                if len(ret)==3:  #如果运算式的长度为3， 说明可以进行运算
                    sum2(ret) #调用递归算法，计算该列表
                elif ret[0]=="-":  #如果运算式的第一个字符为减号，则跳过
                    pass
                elif len(ret)>=3 and q4.isalnum()==False:  #如果运算式的长度等于大于3 并且包含非数字（包含运算符）
                    q5=re.findall("[[0-9.]+|[+\-*/]",q4)  #将q4 生成可以计算的列表形式
                    sum2(q5)  #调用递归算法，计算该列表
                    ret.pop(index) #将当前索引元素移除
                    ret.insert(index,temp[-1])  #将计算出的结果值插入当前位置
                    if len(ret)>=3:  #如果算式的长度还大于等于3
                        sum2(ret)  #则继续递归

        #elif  mark == "*" or mark=="/":
        elif str(mark) in "*/":  #如果字符串元素中包含运算符 */乘法 和除法
            if (len(ret))>=3:  #如果算式长度大于等于3
                x=float(ret.pop(index-1))  #取出一个元素并移除，转化为浮点型
                i=ret.pop(index-1)  #取出一个元素并移除 这个是 运算符
                y=ret.pop(index-1) #取出一个元素并移除，转化为浮点型
                y11=y  #将y赋值给y11
                if "(" in str(y):
                    y12 = re.findall('\([^()]+\)', y11)  #说明该元素中还包含括号，需要继续运算
                    for index12, gg in enumerate(y12):  #遍历该元素
                        t2 = y12[0]
                        r1 = re.findall('^\(\-[0-9.]+|[0-9.]+|[*/+]|[-]', y12[0])
                        y14 = re.findall('\((.+)\)', y12[0])
                        h = float(re.sub('\(', '', r1.pop(0)))
                        r1.insert(0, h)
                        r2 = re.findall('^\(\-[0-9.]+|[0-9.]+|[*/+]|[-]', y14[0])
                        # mark4 = str(t2).count("(-")==1 ? r1:r2
                        y13 = r1 if str(t2).count("(-") == 1 else r2  #三目运算

                        sum2(y13)
                        y11 = y11.replace(str(y12[0]), str(temp[-1]))
                        y12.pop(0)
                        y12.append(temp[-1])
                        y15 = re.findall('[0-9.]+|[*+/]|\([^()]+\)+|\(.+\)+|[\-]', y11)
                        sum2(y15)
                        y=temp[-1]  #将最终结果数字赋给y

                y=float(y)  #转化为浮点型

            if  str(mark)=="*":  #如果元素mark 包含乘号 *
                s=multiply(x,y)  #调用乘法计算公式
                ret.insert(index-1,s)  #将结果插入当前索引算式的位置
                temp.append(s)   #将乘积存储在临时列表中
                if len(ret)>=3:   #如果算式列表的长度还大于等于3
                    sum2(ret)   #调用递归算法，计算该列表
            if str(mark) == "/": #如果元素mark 包含除号 /
                s=divide(x,y)
                temp.append(s)
                ret.insert(index - 1, s)
                if len(ret)>=3:
                    sum2(ret)

    if len(ret)>=3:   #如果算式列表的长度还大于等于3
        x=ret.pop(0)  #取出移除第一个元素
        w2 = re.findall('[0-9.]+|[+\-*/]', str(x))  #将该元素生成可以计算的列表形式
        if str(x)=="-":  #如果x中包含 -号
            x=str(x)+str(ret.pop(0)) #将当前和下一个元素合并 （形成负数）
        if len(w2) >= 4:  #如果x中包含多个算式
            sum2(w2)  #调用递归算法，计算该列表
            x = temp[-1]  #将计算的结果赋给x

        x=float(x)
        i=ret.pop(0)
        y=ret.pop(0)
        if str(y)=="-":
            y=y+str(ret.pop(0))
        y =float(y)
        if i in "*/()":
           return
        else:
            if i in "+":  #如果i包含 加号+
                s = add(x, y)
                temp.append(s)
            elif i in "-":  #如果i包含 加号-
                s= subtract(x,y)
                temp.append(s)
        s=temp[-1]  #将得出的结果赋给s
        if len(ret) >= 2:  #算式的长度大于等于2，说明还要继续计算
            ret.insert(0,s)  #将该结果插入到算式中
            sum2(ret)
    return temp[-2]  #将临时数值列表中的 最后一个值返回，该值就是最终结果

def  sum():
        arg = input("请输入算式(只能包含数值，小括号，+-*/):")  #输入提示
        print("您输入的算式为：", arg)
        arg = re.sub('\s', '', arg) #将空格全部替换
        arg1= re.match('[(\).+\-*/0-9]+$', arg)  #判断输入的是否符合要求

        if arg1: #如果符合要求，则执行下一步
            #print(arg1.group())
            pass
        else:  #如果不符合，重试进入程序
            print("您输入的包含非法字符,请重新输入！")
            arg=""
            sum()

        if str(arg).count("(")!=str(arg).count(")"):  #如果输入的括号对 数量不对，重新输入
            print("您输入的括号对数有误,请重新输入！")
            arg = ""
            sum()
        arg2="'"+arg+"'"
        #print("计算机结果为：",eval(arg2))
        ret=re.findall('\(.*\)|[0-9.]+|[*/+]|[-]',arg)  #将字符串初始成可以计算的列表形式
        j=sum2(ret)  #调用函数
        return j

x1 = sum()  #调用函数
print("结果：", x1)
 
完毕！

上节实现了计算器的界面，这节实现核心算法，下节实现用户界面与业务逻辑的分离
 
目录
 
1、分离算法
 
2、括号匹配算法 
 
3、中缀转后缀算法
 
4、后缀表达式计算 
 
5、完整代码
 

分离算法：将中缀表达式进行数字和运算符的分离 
 
中缀转后缀算法：将中缀表达式转换为后缀表达式 
 
后缀表达式计算 ：通过后缀表达式计算最终结果 
 
1、分离算法
 
思想：以符号作为标志对表达式中的字符逐个访问
 
    - 初始累计变量num为空，遍历字符串每个字符
 
    - 若遇到数字或小数点（即当前符号是数字的一部分），累加到num变量，并用pre变量记录当前符号（用来判断正负号）
 
    - 若遇到其它符号（+， -， *， / ， ( ， ) ，+， -）
 
         ✔ 先看num变量，若有值，num的值放入队列，清空num
 
         ✔ 若为正负号，累计到num变量（流程能走到这说明num无值）
 
         ✔ 否则当前字符（即运算符或括号）入队列
 
         ✔ pre记录当前字符
 
    - 遍历结束后若num不为空，入队列（遍历的最后一个字符是数字还没机会入队列）
 
 
 
  
 
区分正负号和加减号准则：正负号 + 和 - 在表达式的第一个位置、括号后的 + 和 - 、运算符后的 + 和 -
 
bool QCalculatorDec::isDigitOrDot(QChar c)
{
    return (('0' <= c) && (c <= '9')) || (c == '.');
}

bool QCalculatorDec::isSymbol(QChar c)
{
    return isOperator(c) || (c == '(') || (c == ')');
}

bool QCalculatorDec::isSign(QChar c)
{
    return (c == '+') || (c == '-');
}

bool QCalculatorDec::isNumber(QString s)
{
    bool ret = false;

    s.toDouble(&ret);

    return ret;
}

bool QCalculatorDec::isOperator(QString s)
{
    return (s == "+") || (s == "-") || (s == "*") || (s == "/");
}

bool QCalculatorDec::isLeft(QString s)
{
    return (s == "(");
}

bool QCalculatorDec::isRight(QString s)
{
    return (s == ")");
}

int QCalculatorDec::priority(QString s)
{
    int ret = 0; // 其他符号的优先级最低

    if( (s == "+") || (s == "-") )
    {
        ret = 1;
    }

    if( (s == "*") || (s == "/") )
    {
        ret = 2;
    }

    return ret;
}

QQueue<QString> QCalculatorDec::split(const QString& exp)
{
    QQueue<QString> ret;
    QString num = "";
    QString pre = "";

    for(int i=0; i<exp.length(); i++)
    {
        if( isDigitOrDot(exp[i]) )
        {
            num += exp[i];
            pre = exp[i];
        }
        else if( isSymbol(exp[i]) )
        {
            if( !num.isEmpty() )
            {
                ret.enqueue(num);

                num.clear();
            }

            if( isSign(exp[i]) && ((pre == "") || (pre == "(") || isOperator(pre)) )
            {
                num += exp[i];
            }
            else
            {
                ret.enqueue(exp[i]);
            }

            pre = exp[i];
        }
    }

    if( !num.isEmpty() )
    {
        ret.enqueue(num);
    }

    return ret;
}
 
 
 
 
2、括号匹配算法 
 
合法的四则运算表达式中 ，括号匹配成对出现 ，左括号必然先于右括号出现
 
          
 
bool QCalculatorDec::match(QQueue<QString>& exp)
{
    bool ret = true;
    int len = exp.length();
    QStack<QString> stack;

    for(int i=0; i<len; i++)
    {
        if( isLeft(exp[i]) )
        {
            stack.push(exp[i]);
        }
        else if( isRight(exp[i]) )
        {
            if( !stack.isEmpty() && isLeft(stack.top()) )
            {
                stack.pop();
            }
            else
            {
                ret = false;
                break;
            }
        }
    }

    return ret && stack.isEmpty();
}
 
3、中缀转后缀算法
 
中缀表达式：9.3 + ( 3 - -0.11 ) * 5 + 10
 
后缀表达式：9.3    3     -0.11    -      5     *    10     +    +
 
流程：
 
9.3 为数字，直接输出
+ 为运算符且栈为空，入栈
(  为左括号，入栈
3是数字，直接输出
- 是运算符，大于栈顶优先级，入栈
-0.11 是数字，直接输出
)  为右括号，不断弹出栈顶，直到遇到左括号与当前的右括号匹配
* 为运算符，大于栈顶优先级，入栈（后缀的表现形式为 num1 num2 op， 运算符始终在最后，当前的运算符优先级高， 先参与计算 ）
5 为数字，直接输出
+ 为运算符，小于栈顶优先级，栈顶出栈输出，+入栈（后缀的表现形式为 num1 num2 op， 运算符始终在最后，当前的运算符优先级低， 后参与计算 ）
10是数字，直接输出
此时栈不为空，全部输出
验证：从左到右分别将操作符的左边的两个数字与操作符进行运算
 
转换过程： 
 
    - 当前元素e为数字，输出到队列 
 
    - 当前元素e为运算符： 先与栈顶运算符进行优先级比较 
 
             ✔ 小于等于：将栈顶元素输出到队列
 
             ✔ 将当前元素e入栈 
 
    - 当前元素e为左括号：入栈 
 
    - 当前元素e为右括号： 
 
         1. 弹出栈顶元素并输出到队列，直至栈顶元素为左括号 
 
         2. 将栈顶的左括号从栈中弹出
 
bool QCalculatorDec::transform(QQueue<QString>& exp, QQueue<QString>& output)
{
    bool ret = match(exp);
    QStack<QString> stack;

    output.clear();

    while( ret && !exp.isEmpty() )
    {
        QString e = exp.dequeue();

        if( isNumber(e) )
        {
            output.enqueue(e);
        }
        else if( isOperator(e) )
        {
            while( !stack.isEmpty() && (priority(e) <= priority(stack.top())) )
            {
                output.enqueue(stack.pop());
            }

            stack.push(e);
        }
        else if( isLeft(e) )
        {
            stack.push(e);
        }
        else if( isRight(e) )
        {
            while( !stack.isEmpty() && !isLeft(stack.top()) )
            {
                output.enqueue(stack.pop());
            }

            if( !stack.isEmpty() )
            {
                stack.pop();
            }
        }
        else
        {
            ret = false;
        }
    }

    while( !stack.isEmpty() )
    {
        output.enqueue(stack.pop());
    }

    if( !ret )
    {
        output.clear();
    }

    return ret;
}
 
 
 
 
4、后缀表达式计算 
 
遍历后缀表达式中的数字和运算符 
 
    - 当前元素为数字，进栈 
 
    - 当前元素为运算符： 
 
         1. 从栈中弹出右操作数 
 
         2. 从栈中弹出左操作数 
 
         3. 根据符号进行运算 
 
         4 将运算结果压入栈中 
 
遍历结束 
 
    - 栈中的唯一数字为运算结果
 
QString QCalculatorDec::calculate(QString l, QString op, QString r)
{
    QString ret = "Error";

    if( isNumber(l) && isNumber(r) )
    {
        double lp = l.toDouble();
        double rp = r.toDouble();

        if( op == "+" )
        {
            ret.sprintf("%f", lp + rp);
        }
        else if( op == "-" )
        {
            ret.sprintf("%f", lp - rp);
        }
        else if( op == "*" )
        {
            ret.sprintf("%f", lp * rp);
        }
        else if( op == "/" )
        {
            const double P = 0.000000000000001;

            if( (-P < rp) && (rp < P) )
            {
                ret = "Error";
            }
            else
            {
                ret.sprintf("%f", lp / rp);
            }

        }
        else
        {
            ret = "Error";
        }
    }

    return ret;
}

QString QCalculatorDec::calculate(QQueue<QString>& exp)
{
    QString ret = "Error";
    QStack<QString> stack;

    while( !exp.isEmpty() )
    {
        QString e = exp.dequeue();

        if( isNumber(e) )
        {
            stack.push(e);
        }
        else if( isOperator(e) )
        {
            QString rp = !stack.isEmpty() ? stack.pop() : "";
            QString lp = !stack.isEmpty() ? stack.pop() : "";
            QString result = calculate(lp, e, rp);

            if( result != "Error" )
            {
                stack.push(result);
            }
            else
            {
                break;
            }
        }
        else
        {
            break;
        }
    }

    if( exp.isEmpty() && (stack.size() == 1) && isNumber(stack.top()) )
    {
        ret = stack.pop();
    }

    return ret;
}
 
5、完整代码
 
QCalculatorDec.h
 
#ifndef _CALCULATORCORE_H_
#define _CALCULATORCORE_H_

#include <QString>
#include <QStack>
#include <QQueue>

class QCalculatorDec
{
protected:
    QString m_exp;
    QString m_result;

    bool isDigitOrDot(QChar c);
    bool isSymbol(QChar c);
    bool isSign(QChar c);
    bool isNumber(QString s);
    bool isOperator(QString s);
    bool isLeft(QString s);
    bool isRight(QString s);
    int priority(QString s);
    bool match(QQueue<QString>& exp);
    QString calculate(QQueue<QString>& exp);
    QString calculate(QString l, QString op, QString r);
    bool transform(QQueue<QString>& exp, QQueue<QString>& output);
    QQueue<QString> split(const QString& exp);
public:
    QCalculatorDec();
    ~QCalculatorDec();
    bool expression(const QString& exp);
    QString expression();
    QString result();
};

#endif
 
QCalculatorDec.cpp
 
#include "QCalculatorDec.h"

QCalculatorDec::QCalculatorDec()
{
    m_exp = "";
    m_result = "";
}

QCalculatorDec::~QCalculatorDec()
{

}

bool QCalculatorDec::isDigitOrDot(QChar c)
{
    return (('0' <= c) && (c <= '9')) || (c == '.');
}

bool QCalculatorDec::isSymbol(QChar c)
{
    return isOperator(c) || (c == '(') || (c == ')');
}

bool QCalculatorDec::isSign(QChar c)
{
    return (c == '+') || (c == '-');
}

bool QCalculatorDec::isNumber(QString s)
{
    bool ret = false;

    s.toDouble(&ret);

    return ret;
}

bool QCalculatorDec::isOperator(QString s)
{
    return (s == "+") || (s == "-") || (s == "*") || (s == "/");
}

bool QCalculatorDec::isLeft(QString s)
{
    return (s == "(");
}

bool QCalculatorDec::isRight(QString s)
{
    return (s == ")");
}

int QCalculatorDec::priority(QString s)
{
    int ret = 0;

    if( (s == "+") || (s == "-") )
    {
        ret = 1;
    }

    if( (s == "*") || (s == "/") )
    {
        ret = 2;
    }

    return ret;
}

bool QCalculatorDec::expression(const QString& exp)
{
    bool ret = false;
    QQueue<QString> spExp = split(exp);
    QQueue<QString> postExp;

    m_exp = exp;

    if( transform(spExp, postExp) )
    {
        m_result = calculate(postExp);

        ret = (m_result != "Error");
    }
    else
    {
        m_result = "Error";
    }


    return ret;
}

QString QCalculatorDec::result()
{
    return m_result;
}

QQueue<QString> QCalculatorDec::split(const QString& exp)
{
    QQueue<QString> ret;
    QString num = "";
    QString pre = "";

    for(int i=0; i<exp.length(); i++)
    {
        if( isDigitOrDot(exp[i]) )
        {
            num += exp[i];
            pre = exp[i];
        }
        else if( isSymbol(exp[i]) )
        {
            if( !num.isEmpty() )
            {
                ret.enqueue(num);

                num.clear();
            }

            if( isSign(exp[i]) && ((pre == "") || (pre == "(") || isOperator(pre)) )
            {
                num += exp[i];
            }
            else
            {
                ret.enqueue(exp[i]);
            }

            pre = exp[i];
        }
    }

    if( !num.isEmpty() )
    {
        ret.enqueue(num);
    }

    return ret;
}

bool QCalculatorDec::match(QQueue<QString>& exp)
{
    bool ret = true;
    int len = exp.length();
    QStack<QString> stack;

    for(int i=0; i<len; i++)
    {
        if( isLeft(exp[i]) )
        {
            stack.push(exp[i]);
        }
        else if( isRight(exp[i]) )
        {
            if( !stack.isEmpty() && isLeft(stack.top()) )
            {
                stack.pop();
            }
            else
            {
                ret = false;
                break;
            }
        }
    }

    return ret && stack.isEmpty();
}

bool QCalculatorDec::transform(QQueue<QString>& exp, QQueue<QString>& output)
{
    bool ret = match(exp);
    QStack<QString> stack;

    output.clear();

    while( ret && !exp.isEmpty() )
    {
        QString e = exp.dequeue();

        if( isNumber(e) )
        {
            output.enqueue(e);
        }
        else if( isOperator(e) )
        {
            while( !stack.isEmpty() && (priority(e) <= priority(stack.top())) )
            {
                output.enqueue(stack.pop());
            }

            stack.push(e);
        }
        else if( isLeft(e) )
        {
            stack.push(e);
        }
        else if( isRight(e) )
        {
            while( !stack.isEmpty() && !isLeft(stack.top()) )
            {
                output.enqueue(stack.pop());
            }

            if( !stack.isEmpty() )
            {
                stack.pop();
            }
        }
        else
        {
            ret = false;
        }
    }

    while( !stack.isEmpty() )
    {
        output.enqueue(stack.pop());
    }

    if( !ret )
    {
        output.clear();
    }

    return ret;
}

QString QCalculatorDec::calculate(QString l, QString op, QString r)
{
    QString ret = "Error";

    if( isNumber(l) && isNumber(r) )
    {
        double lp = l.toDouble();
        double rp = r.toDouble();

        if( op == "+" )
        {
            ret.sprintf("%f", lp + rp);
        }
        else if( op == "-" )
        {
            ret.sprintf("%f", lp - rp);
        }
        else if( op == "*" )
        {
            ret.sprintf("%f", lp * rp);
        }
        else if( op == "/" )
        {
            const double P = 0.000000000000001;

            if( (-P < rp) && (rp < P) )
            {
                ret = "Error";
            }
            else
            {
                ret.sprintf("%f", lp / rp);
            }

        }
        else
        {
            ret = "Error";
        }
    }

    return ret;
}

QString QCalculatorDec::calculate(QQueue<QString>& exp)
{
    QString ret = "Error";
    QStack<QString> stack;

    while( !exp.isEmpty() )
    {
        QString e = exp.dequeue();

        if( isNumber(e) )
        {
            stack.push(e);
        }
        else if( isOperator(e) )
        {
            QString rp = !stack.isEmpty() ? stack.pop() : "";
            QString lp = !stack.isEmpty() ? stack.pop() : "";
            QString result = calculate(lp, e, rp);

            if( result != "Error" )
            {
                stack.push(result);
            }
            else
            {
                break;
            }
        }
        else
        {
            break;
        }
    }

    if( exp.isEmpty() && (stack.size() == 1) && isNumber(stack.top()) )
    {
        ret = stack.pop();
    }

    return ret;
}
 
main.cpp
 
#include <QtGui/QApplication>
#include "QCalculatorDec.h"

#include <QDebug>

int main(int argc, char *argv[])
{
    
    QCalculatorDec c;

    c.expression(" (5 - 8) * (5 - 6) ");

    qDebug() << c.result();

    return 0;
}
 
 

 
昨天 论坛里一个学生问我了一个四则运算的程序,是他抄来的.他可能是看不懂.我看了半天也很迷茫..
 
因为他不直到超的谁的,变量名字没有任何含义,类似cc,jj,a,f等...看起来比较累.所以我就注释了一下.
 
结果发现程序虽然乱，但是这位朋友写的东西真的满有意思呢..新手看了也许会有所收获吧.
 
现在太晚了,先发其中一个函数,也是有点含量的..新手可以看看,老鸟不要鄙视我..
 
/*-------------------------------------------------------------------------------------------
 
函数名称:double convnum(char *c)
 
函数功能:把一个字符串,比如"8.87"转化成一个数字,双字节类型浮点
 
返回值  :浮点型
 
-------------------------------------------------------------------------------------------*/
 
double convnum(char *c)
 
{
 
double num = 0.0;                                //用于存放中间变量和最终输出的值
 
double a   = 1.0;                                //用于求小数位
 
int i=0,p=0,len=0;                                //i  :for循环通用变量,国际惯例
 
//p  :如果该数据是小数,则存放小数点在该数组中的位置
 
//len:遍历字符串,存放字符串的长度
 
//***NOTE***
 
//建议改为unsigned char 型,
 
//世界上没有超过256长度的数字吧.....
 
//至少你的计算器显示不下,占空间,影响程序执行速度
 
char idata temp[10];                        //如果是整数,则存放整个数据,
 
//如果是小数,则存放数据的整数部分
 
//***NOTE***
 
//从这里可以看出这个数据的整数部分不超过10位数
 
int tempi=0;                                        //temp数组使用的下标计数器        //可改为unsigned char
 
int start=0;                                        //如果是负数的时候它等于1        //可改为unsigned char
 
int f=1;                                                   //如果是负数的时候它等于-1        //可改为char
 
len=strlen(c);                                        //求字符串长度
 
/* 如果是负数 */
 
if(c[0]=='-')
 
{
 
start=1;                                        //下面对于字符串的遍历工作,从字符串的c[1]位开始,
 
//执行这句的前提是字符串所代表的是个负数,第一位
 
//被负号占用了
 
f=-1;
 
}
 
/*遍历字符串,如果有小数,则退出*/
 
for(i=start; i
 
{
 
if(c=='.')
 
{
 
p=i;
 
break;                                        //如果碰到 . 则这个数是小数 退出.
 
//此时,temp[]中保存了整数部分
 
//如果一直没有碰到 . 这个数就是整数了
 
//temp[]中完整的保留了这个数的每一位
 
}
 
temp[tempi++]=c;
 
}
 
temp[tempi]='\0';                                //因为后面要求temp 这个字符串的长度,所以加个字符串结束符
 
/* 如果p!=0,这个数将是个小数,这里求小数部分,如果是整数,P==0 */
 
if(p!=0)
 
{
 
for(i=p+1;i
 
{
 
if(c=='.')                         //一个数字中不可能出现两个小数点,如果出现,数据非法,退出.
 
{
 
// printf("there is more that one dot '.' in number!error!\n");
 
//    exit(0);
 
}
 
a=a*0.1;                                //注意a的初值是1,循环每走一圈,a缩小10倍--0.1,0.01,0.001....
 
num+=(a*(c-48));                //这里是最常用的技巧了.
 
//num初值是0,假设这个数据的小数部分是0.87
 
//循环第一圈: a = 0.1  , c= 8 , num = 0.1 * 8 + 0 = 0.8
 
//循环第二圈: a = 0.01 , c= 7 , num = 0.01 *7 + 0.8 = 0.87
 
}
 
}
 
a=1.0;
 
len=strlen(temp);
 
/* 计算整数部分 */
 
for(i=len-1;i>=0; i--)                        //这次是倒着来的,从个位开始,
 
//为什么要len - 1?因为数组的长度如果是5,那么下标一定是4,总是少一个,
 
//因为数组的下标会出现 0
 
{
 
num=num+(a*(temp-48));        //
 
a*=10;                                                //用求小数部分的思路去理解这里很简单.每一圈a 扩大10倍,
 
}
 
num=num*f;                                                //如果是负数,f = -1,则最终输出的数就会变成负数.
 
return num;
 
}
 
哎,我那完美的缩进格式......上文件了
 
缩进是4个字符,这个看起来舒服ourdev_631928FUOY30.rar(文件大小:2K) (原文件名:main.rar)
 
明天继续上传,核心的算法,是用递归一次又一次的消除掉字符串里的括号.